求素数常用的几种方法_求素数的数学方法

如何判断素数一个素是不是素数呢？或许你会以为这是一个非常简单问题，就像1+1=2一样，当一个数的因子只有1和它本身的时候就是素数，很简单的嘛！！！但是，当一个数特别大的时候就没有那么简单进行判断了。

下面我们就求素数常用的一些方法进行讨论和判断。

我们先来看看幼稚园的小孩子的做法：

#include<stdio.h>
#include<time.h>
int IsPrime(int n){
	int i;
	if(n <= 1){
		return 0;
	}
	if(n==2){
		return 1;
	}
	for(i = 2;i < n;i++){
		if(n%i==0) return 0;
	}
	return 1; 
}
int main(){
	int n,i;
	int t1 = clock();
	for(i = 0;i<=100000;i++){
		if(IsPrime(i)) printf(" %d ",i);
	}
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

下面我们来看稍微聪明一点点的幼稚园的做法：

#include<stdio.h>
#include<time.h>
int IsPrime(int n){
	int i;
	if(n <= 1){
		return 0;
	}
	if(n==2){
		return 1;
	}
	for(i = 2;i <= n/2;i++){
		if(n%i==0) return 0;
	}
	return 1; 
}
int main(){
	int n,i;
	int t1 = clock();
	for(i = 0;i<=100000;i++){
		if(IsPrime(i)) printf(" %d ",i);
	}
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

因为2*3=6和3*2=6效果是一样的，所以我们只要对它的前一半的数进行判断就可以了，后面的就可以不用判断了。

下面我们来看比较聪明的幼稚园做法：

#include<stdio.h>
#include<time.h>
int IsPrime(int n){
	int i;
	if(n==2){
		return 1;
	}
	if(n <= 1||n%2==0){
		return 0;
	}
	
	for(i = 3;i <= n/2;i+=2){
		if(n%i==0) return 0;
	}
	return 1; 
}
int main(){
	int n,i;
	int t1 = clock();
	for(i = 0;i<=100000;i++){
		if(IsPrime(i)) printf(" %d ",i);
	}
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

#include<stdio.h>
#include<time.h>
int IsPrime(int n){
	int i;
	for(i = 3;i <= n/2;i+=2){
		if(n%i==0) return 0;
	}
	return 1; 
}
int main(){
	int n,i;
	int t1 = clock();
	printf(" 2 "); 
	for(i = 3;i<=100000;i+=2){
		if(IsPrime(i)) printf(" %d ",i);
	}
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

接下来我们看比较聪明的小学生的做法：

#include<stdio.h>
#include<time.h>
#include<math.h>
int IsPrime(int n){
	int i;
	if(n%2==0) return 0;
	for(i = 3;i <= sqrt(n);i+=2){
		if(n%i==0) return 0;
	}
	return 1; 
}
int main(){
	int n,i;
	int t1 = clock();
	printf(" 2 "); 
	for(i = 3;i<=100000;i++){
		if(IsPrime(i)) printf(" %d ",i);
	}
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

而如果只调用sqrt()函数的话，只需要计算一次。故还是sqrt()函数好一些啊。

确实，对于一个小学生，能够这么牛逼的想到这么多优化，

已经很强大了。

不过其实没什么必要。。。。。。

这里的i+=2，是因为，偶数除了2之外，是不可能是素数的、

所以从3开始，直接+2 。进一步优化。

这个大概就是朴素判断素数方法的最佳优化了。（也许你还有更好的优化）

所以，如果是对于一般的素数判断的话，用上面那个代码吧

小学生毕业了，到了中学，会有怎样的成长呢？

下面来看看中学生们是怎么样判断的。

BY：Lw

是针对自然数列中的自然数而实施的，用于求一定范围内的质数，

它的容斥原理之完备性条件是p=H~。

可参考：

http://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89

%B9%E5%B0%BC%E7%AD%9B%E6%B3%95

基本原理：

筛素数的基本方法是用来筛选出一定范围内的素数素数筛法的基本原理，利用的是素数p只有1和p

这两个约数，并且一个数的约数一定不大于本身，素数筛法的过程：

把从1开始的、某一范围内的正整数从小到大顺序排列，

1不是素数，首先把它筛掉。

剩下的数中选择最小的数是素数，然后去掉它的倍数。

依次类推，直到筛子为空时结束。

求解用途：

素数筛法经常作为一道题的一部分用来打一定范围内素数表，

然后利用素数表作为基础解题。

#include<stdio.h>
#include<time.h>
#include<math.h>
#define N 100000
int prime[100000];
void init(){
	int i,j;
	for(i = 2;i <=N ;i++){
		prime[i] = 1;
	}
	for(i = 2;i <= N;i++){
		if(prime[i]) printf(" %d ",i);
		for(j = i+i;j <= N;j += i) prime[j] = 0;
	}
}
int main(){
	int n,i;
	int t1 = clock();
	init();
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

所以呢，这个算法执行完一遍之后，就可以在O(1)的时间内判断出N以内的任意数，是不是素数

了，所以这个算法消耗的时间可以说全部在筛选上了。初看这个算法，会觉得这个算法的时间复杂

度是O(N^2)，，但其实不是的，在第二个循环中，每次递增的i，当i越来也大的时候，j很快就能超

过N的，筛选法的实际复杂度是O(n*log(logn)）。

到这里你可能会说中学生也不过如此嘛，运行效率和聪明的小学生差不多，不要急，这只是最基础的中学生做法

下面我们一起来看看比较有思想的中学生的做法：

#include<stdio.h>
#include<time.h>
#include<math.h>
#define N 100000
int prime[100000];
int a[N];
void init(){
	int i,j,len=0;
	for(i = 0;i <N ;i++){
		prime[i] = 0;
	}
	for(i = 2; i <= N; i++)
	{
		if(!prime[i]){
			a[len++] = i;
			printf(" %d ",i);
		} 
		for(j = 0; j< len &&a [j]*i <= N; j++)
		{
			prime[a[j]*i] = 1;
			if(i % a[j] == 0) break;
		}
	}
 
 
}
int main(){
	int n,i;
	int t1 = clock();
	init();
	int t2 = clock();
	printf("\n运行时间：%d\n",t2-t1);
} 

这个算法的关键在于if(i % a[j] == 0) break;，它使得任何一个合数，只能被它最小的质因数标记过

一次，再一次进行优化。所以整个算法是线性的。但考虑到log(log(100000000))还不到3，

故这个线性算法其实也只有理论的价值罢了。

其实我不这样认为。这样其实可以当成素数表来用，因为定义了一个数组p，存放的都是素数。

讲到这里，你应该对判断素数这个问题有了一个新的认识了。

既要考虑时间上的问题。又要考虑空间上的问题。

也就是这并不是一个无脑问题。