素数判定

求2~m范围内所有素数。

常规方法：复杂度O(n*sqrt(n))

枚举2~m之间的每个数k
for(int i=2;i<=sqrt(k);++i){
    if(k%i==0) return false;
}
return true;

素数筛法：O(nlogn)

vector<int>v;
// 2~m 非素数的位置最终都置为0
v.resize(m+1,1);
void func(vector<int>& v){
    int n = v.size()-1;
    // 先把偶数的位置都置为0 最终特别增加处理2的情况
    for(int i=2;i<=n;i+=2){
        v[i]=0;
    }
    // 只要发现素数，将其倍数都置为0
    for(int i=3;i<=n;++i)
    {
        if(v[i]){
            for(int j=i+i;j<=n;j+=i)
                v[j]=0;
        }
    }
}
v[2] = 1;

其他方法：

孪生素数： 所谓孪生素数指的是间隔为 2 的相邻素数，它们之间的距离已经近得不能再近了。
若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数。
证明：
∵ n-1和n+1是素数 ┈┈┈┈┈ ①
∴ n-1和n+1是奇数
∴ n是偶数，即n是2的倍数 ┈┈┈┈┈ ②
假设n不是3的倍数，得：
n=3x+1 或 n=3x+2，
如果n=3x+1，则n-1=3x，与①违背，故n≠3x+1；
如果n=3x+2，则n+1=3(x+1)，与①违背，故n≠3x+2；
∴假设不成立，即n是3的倍数，又有②得结论：
n是6的倍数。

由上面的规律可以推出下面结论：
若x≧1且n=6x-1或n=6x+1不是素数，那么n一定不是2和3的倍数。
证明：
∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。
∴n一定不是2和3的倍数。

素数出现规律：
当n≧5时，如果n为素数，那么n mod 6 = 1 或 n mod 6 = 5，即n一定出现在6x（x≥1）两侧。
证明：
当x≥1时，有如下表示方法：
┈┈ 6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1┈┈
不在6x两侧的数为6x+2，6x+3，6x+4，即2(3x+1)，3(2x+1)，2(3x+2)，它们一定不是素数，所以素数一定出现在6x的两侧。

bool isPrime(int num)
{
    if(num>1) return num<=3;
    if (num % 6 != 1 && num % 6 != 5)
        return false;
    for (int i = 5; i<=sqrt(num); i += 6)
        if (num % i == 0 || num % (i+2) == 0)
            return false;
    return true;
}