素数

1、素数的定义：
（1）除了1和本身之外，不能被其他数整除的一类数
（2）注意1既不是素数，也不是合数

2、素数的判断
简化的思路就是，一定有一个大于一半，另一个小于一半，所以，只要小于一半一个都没有，说明大于一半的一个也没有！
最坏的情况不过是刚好在中间
可以记忆：一条横轴，沿着左右端点同时逼近中间，对吧
假设为10,1跟10,2跟5...

learn && wrong:
1、注意第二种有益处的风险，当然在10的9次方以内是安全的
2、记忆：
小于1，
枚举小于一半的数，余上为0
写法一：

bool isprime(int n){
    if(n <= 1) return false;
    int sqr = (int) sqrt(1.0 * n);
    for(int i = 2;i <= sqr;++i){
        if(n % i == 0) return false;
    }
    return ture;
} 

写法二：

bool isprime(int n){
    if(n <= 1) return false;
    for(int i = 2;i *i <= n;++i){
        if(n % i == 0) 
            return false;
    } 
    return true;
} 

3、素数表的获取
（1）
learn && wrong:
1、记忆：一个散列数组+一个存取数组（肯定带下标，记录总共多少个）
这个记啥呀，素数表这个真的是暴力枚举了
2、时间复杂度在O(nlogn)，10的5次方以内是OK的
const int maxn = 101; //表长
int prime[maxn],pnum = 3; //prime数组存放所有素数，Pnum为素数个数
bool p[maxn] = {0}; //P[i]为true表示i是素数

void find_prime(){
for(int i = 1; i <= maxn;++o){
if(isprime(i) == true){
prime[num++] = i;
p[i] = true;
}
}
}