素数（质数）の千层套路

素数（质数）の千层套路

素数（质数）の千层套路

假如给你以一个正整数N，你能否找到1~n之间所有的素数？素数的脾气可不好惹。

1.双层循环暴力求值

这个求法没什么好讲的，就是两个for循环嵌套一下遍历所有的数，代码如下。

void Prime(int n)
{vis[0] = vis[1] = 1;for(int i = 2;i <= n;i++){for(int j = 2;j < i;i++){if(i % j == 0)vis[i] == 1;}}
}

如此一来，N以内的所有素数都被标记成了true，如果想要存在数组里，再写个for循环就可以做到。

2.素数筛

这个是最基础的素数筛，将N以内的所有素数都存到了数组prime里。这个筛法的原理是将所有的数的倍数都标记为ture，那么没有被标记的数i就说明从2~i-1之间没有它的约数，就说明它是质数。

void Prime(int n)
{vis[0] = vis[1] = 1;for(int i = 2;i < n;i++){if(!vis[i]) prime[idx++] = i;for(int j = i + i;j <= n;j += i)vis[j] = 1;}
}

3.埃氏筛

埃氏筛的原理是与上边的类似，但是埃氏筛只标记素数的倍数，时间复杂度大大降低。

void Prime(int n)
{vis[0] = vis[1] = 1;for(int i = 2;i <= n;i++){if(!vis[i]){for(int j = i + i;j <= n;j += i) vis[j] = 1;}}
}

可见所有的素数都被标记了false，如果想要存在数组中，只要将一个数组放到if函数里存i即可。

4.欧拉筛（线性筛）

欧拉筛与埃氏筛的区别就是埃氏筛会对一个非素数重复标记，而欧拉筛会且仅访问一次每个数。在时间复杂度上进一步降低。

void Prime(int n)
{vis[0] = vis[1] = 1;for(int i = 2;i <= n;i++){if(!vis[i]) prime[idx++] = i;for(int j = 0;prime[j] <= n / i;j++){vis[prime[j] * i] = 1;if(i % prime[j] == 0) break;//当前记录的素数最大时i，能够被i整除的只有i本身。}}
}