素数（筛法）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 
 
一定好好理解理解。
 

参考：(3条消息) 筛法求素数_ljh736731592的博客-CSDN博客_筛法求素数https://blog.csdn.net/ljh736731592/article/details/99704431?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164834662716780261957560%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164834662716780261957560&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-99704431.142^v5^pc_search_result_cache,143^v6^register&utm_term=%E7%AD%9B%E6%B3%95%E6%B1%82%E7%B4%A0%E6%95%B0&spm=1018.2226.3001.4187