素数方面知识整理_sqrtn和i*i

---

一、判断素数

int judge(int n){
	if(n==1)return 0;
	for(int i=2;i<=n/i;i++){
		if(n%i==0)return 0;
	}
	return 1;
}
1
2
3
4
5
6
7

注意：以上代码中，for循环的结束条件是 i <= n/i,相当于i <= sqrt(n)，两种写法都可以，只不过调用sqrt()函数会慢一些，因为for循环每次循环都会调用该函数。另外，不能写成i * i <= n
因为当n很接近int的最大值时，i*i可能会溢出。
参考文章

---

二、埃氏筛（埃拉托斯特尼筛法，简称埃氏筛）
应用：求1到n之间的所有素数

暴力求法，遍历[1,n]中所有的数，每次调用判断素数的函数，这种方法，不用说也知道太浪费时间

埃氏筛的思想：一个合数一定能被分解为几个质数的幂的乘积
并且这个数的质因子一定是小于它本身的，所以当我们从小到大将每个质数的倍数都筛去的话，当遍历到一个合数时，它一定已经被它的质因子给筛去了。
比如：

4=2*2
6=2*3
105=3*5*7
1
2
3

const int maxn=10000000;
int a[maxn]={0};
int E_sieve(int n){
	a[1]=1;    		//1是合数，a[]的值为1表示合数，a[]为0表示素数 
	for(int i=2;i<=n;i++){
		if(a[i]==0){
			for(int j=2*i;j<=n;j+=i)	//j表示i的2倍，3倍，... 
				a[j]=1;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

可以对埃氏筛进行优化

1.我们会先筛除2的倍数，然后筛除3的倍数，但是当3筛除6、12、18...时,它们已经被2筛除过了，所以进行了
重复的操作。所以我们可以从i * i开始筛，因为i*2,i*3，i*5...等已经被2*i,3*i,5*i...筛除了。
2.判断一个数是不是素数，只要判断在[2,sqrt（n）]之间有没有它的质因子。
1
2
3

const int maxn=10000000;
int a[maxn]={0};
int E_sieve(int n){
	a[1]=1;    		//1是合数，a[]的值为1表示合数，a[]为0表示素数 
	for(int i=2;i<=n/i;i++){ //只判断2到sqrt(n)之间 
		if(a[i]==0){
			for(int j=i*i;j<=n;j+=i)	//j表示i的i倍，i+1倍，... 
				a[j]=1;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

---

三、欧拉筛（线性筛）
算了，我不写了，直接去膜拜大佬吧
这是大佬
推荐