素数（筛法）c++

求素数3种方法

1，暴力求解

int zhishu(int n)
{
	for(int i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)
		return 0;
	}
	return 1;
}


for(int j=1;j<=m;j++)
zhishu(j);

显然时间复杂度太高了。

2，打表 O(1)（doge)

3，筛法

①埃筛

基础思想：素数的倍数一定不是素数！

实现：从小至大枚举质数x，把x的倍数都标记为非质数。

 

即：

用一个bool型的prime数组memset成0，即一开始假设所有的数都是素数（如果不会memset就用for循环遍历一遍全部初始化成0），然后现在我们有两个已知的非素数（合数）prime[0], prime[1]就将它们初始化成1。

2是第一个素数吧，没问题吧？那现在开始了，循环一遍，把2的倍数全部初始化成1，如果2的某个倍数已经超过了我们给的范围， 就结束循环
接下来找离2最近的素数，3吧，没问题吧？再执行上个循环，3的倍数也变成1了，再从3后面找，4已经被改成1了，那就是5了……
后面一直循环就完了

过程：
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
————————————————

代码：

#include 
#include 
#include 
 
using namespace std;
const int N = 5000010;
bool iprime[N];
int main()
{
    memset(iprime,0,sizeof iprime);
    iprime[0]=1,iprime[1]=1;
    int n;
    cin >> n;
    for(int i=2; i<=sqrt(N); i++)
    {
        if(iprime[i]==1) continue;
        for(int j=i; j*i

一定好好理解理解。