筛法求素数

求素数

显然，可以暴力

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);

显然，复杂度为O(n（sqrt（n）)的。

复杂度太高。

我会O(1)方法——打表

介绍两种O(n)的算法。

一、Eratosthenes

——（埃筛）

1.基本思想：

质数的倍数一定不是质数。

2.实现方法：

从小至大枚举质数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了……

后面一直循环就完了

然后主函数里调用一下，输出!prime[i]，的i。范围内所有的素数都出来了吧，

3.具体过程：

2,3,4,5,6,7,8,9,10,