素数的求解逐步改进

我的注释都写在代码里面了，就不在赘述了！如果有任何疑问欢迎留言

参考博客：

1.位操作总结：http://blog.csdn.net/morewindows/article/details/7354571

2.找素数算法总结：http://blog.csdn.net/hexiios/article/details/4400068

非常感谢上面两篇博客的仁兄，致谢！

尤其是读了位操作的那篇文章，写的非常好，希望各位都可以一次尝试哈，没准给你的程序增加一个亮点

2的总结也很好，我只是在它的基础上在详细的给了些注释，如果有不懂的地方就好理解了！

 

1.基础补习

什么是合数？什么是素数？百度一下你就知道

 

有一个重要的性质:任何一个合数一定可以表示成若干个素数之积。

如：4 = 2 * 2，6 = 2 * 3，12 = 2 * 2 * 3。也就是说，合数N一定是小于N的某个（或若干）素数的整数倍,反之，如果N不是任何比它小的素数的倍数，则N必然是素数。

这个性质就决定了下面的算法基本思想

 

 

2.检查是否是素数（这个是从基本概念出发的检测算法）

主要的改进就是检测的范围缩小从0---sqrt(n)

 

bool isPrime(int n){
	if(n ==0 || n==1) return 0;
	for(int i=2; i<=sqrt(n); i++){
		if(n%i == 0){
			 cout<<i<<endl;
			 return 0;
		}
	}
	return 1;
}

 

 

3.经典素数求解算法

它对每个数的检测就是利用2的方法

 

/**
	*经典素数求解算法
	*prime[0]中保存素数总个数
	*/
int* getPrime(){
	int prime[LEN] = {0};//判断是否为素数,初始都为素数
	prime[0] = 0; //保存素数的总个数
	for(int n=2; n<LEN; n++){
		bool flag = 1;
		//对每个数A都按照：2到sqrt(A)依次除，看是否整除，如果能则不是素数
		//这样是很低效的m*m<=n也可写成m<=sqrt(n)
		//注意：必须有m*m<=n 中的“=”
		for(int m=2; m*m<=n; m++){
			//如果能整除，不是素数
			if(n%m == 0){
				flag = 0;
				break;
			}
		}
		if(flag){
			prime[0]++;
			prime[prime[0]] = n;
		}
	}
	cout<<"\ncount:"<<prime[0]<<endl;
	return prime;
}

 

 

4.经典算法改进版

其主要的改进的地方就是，检测的思想，前面的检测方法就是2到sqrt(A)依次除，看是否整除

改进的就不同了，它利用了合数的性质，利用已经找到的素数来除，这样大大的减少了需要整除的次数，这个改进不错！

 

/**
	*它是上面经典算法改进版
	*这里prime数组中存的是素数,prime[0]中保存素数总个数
	*获取0-n的所有素数
	*/
int* getPrime1(){
	int prime[LEN] = {0};//判断是否为素数,初始都为素数
	int i, n, flag;
  prime[0] = 0; //保存素数的总个数
  for (n =2 ; n < LEN; n++)
  {
        flag = 1;
        //判断当前n是否被"已经找出的素数"整除（如果能，说明不是素数,根据合数性质）
        //使用条件prime[i] * prime[i] <= n，就是判断一个数A是否是素数的时候，不需要
        //从2-A的所有数都去看是否能整除，只需要看2-sqrt(A)即可，即最终整除位置为sqrt(A),见上面isPrime(int n)
        //这里是用prime[i]去整除，故而只需要prime[i]*prime[i]<=n也可写成prime[i]<=sqrt(n)
        for (i = 1; i <= prime[0] && prime[i] * prime[i] <= n; i++)
        	//如果不是素数，break，flag=0
            if (n % prime[i] == 0)
            {
                flag = 0;
                break;
            }
        //flag=1，则说明是素数，存储
        if (flag)
        {       
            prime[0]++;//素数个数
            prime[prime[0]] = n;//将确定了的素数放入数组
        }
  }
  cout<<"\ncount:"<<prime[0]<<endl;
	return prime;
}

 

 

 

5.厄拉多塞筛算法

所谓厄拉多塞筛算法就是：利用一个空间换时间的思想，利用一个辅助数组来存储素数的位置，然后利用的是筛选法，筛选出素数的倍数

那你就会发出一个疑问？只是筛选出素数的倍数，那是不是还有遗漏啊？这个就看看1的性质吧，即所有合数，都可以分解成若干个素数。

 

*首先，将所有的数组元素设为0，表示没有已知的非素数。

*然后，将已知为非素数（即为已知素数的倍数）的索引对应的数组元素设置为1。

*如果将所有较小素数的倍数都设置为1之后，a[i]仍然保持为0，则可判断它是所找的素数。

 

 

/**
	*厄拉多塞筛算法:prime[0]中保存素数总个数
	*/
int* getPrime2(){
	int count = 0;
	int primes[LEN / 3] = {0}, pi=1;
	int flag[LEN] = {0};//判断是否为素数,初始都为素数
	//0,1不是素数
	flag[0]=1;
	flag[1]=1;
	for(int i=2; i<LEN; i++){
		//倍数必然不是素数，把不是素数的都筛选出来
		if(!flag[i]){
			primes[pi++] = i;
			// 注意：这里只用素数来筛，因为合数筛时肯定被素数筛过了，所以没必要.
			//为什么？因为合数的性质：任何一个合数一定可以表示成若干个素数之积。如：4 = 2 * 2，6 = 2 * 3，12 = 2 * 2 * 3
			//即所有合数，都可以分解成若干个素数。
			for(int j=i; j<LEN; j+=i){
				//为什么9624会出现在素数中？
				//if(j == 9624) cout<<"-----"<<i<<" "<<j<<endl;
				flag[j]=1;
				count++;
			}
		}
	}
	//从count可以看出，对于一个位置重复访问了许多次，可以优化
	cout<<"访问数组总数："<<count<<endl;
	primes[0] = pi - 1;
	cout<<"count:"<<primes[0]<<endl;
	return primes;
}

 

 

 

6，厄拉多塞筛算法改进版

由于对于5来说，最大的缺憾就是利用了辅助数组，那么我们可以减少空间，反正都只是存0,1，为什么不用位来存储呢？这样就大大的减少了空间的浪费了！

首先看看一个为操作的事例：

 

/**
	*用于位测试
	*
	*/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
	//在数组中在指定的位置上写1  
    int b[5] = {0};  //占用连续的20个字节空间(每个int占用4字节)，每个字节8位（1Byte=8bit）
    cout<<sizeof(b)<<" "<<sizeof(int)<<endl;
    int i;  
    //在第i个位置上写1(一共有20*8=160位，现在之使用了40位) 
    for (i = 0; i < 40; i += 3)  
    		//每int占用4字节即32位，当b[0]的32位用完，就b[1]
        b[i / 32] |= (1 << (i % 32));  
    //输出整个bitset  
    for (i = 0; i < 40; i++)  
    {  
    	//将数组依次右移一位，然后和1求与，判断该位是0还是1
        if ((b[i / 32] >> (i % 32)) & 1)  
            putchar('1');  
        else   
            putchar('0');  
    }  
    putchar('\n');  
    return 0;  
	return 0;
}

 在下面的算法中就是利用了上面的操作，只要去看看我第一个链接，里面更详细！

 

 

/**
	*厄拉多塞筛算法改进版:prime[0]中保存素数总个数
	*/
int* getPrime3(){
	int primes[LEN / 3] = {0}, pi=1; //实际素数的个数最多就是LEN / 3,故而没用LEN
	//用位替代int prime[LEN] = {0};//判断是否为素数,初始都为素数
	int flag[LEN/32] = {0};//每个int是4字节=32bit（32位）可以存储32个0,1，故而只需要LEN/32个长度的数组即可
	for(int i=2; i<LEN; i++){
		//倍数必然不是素数，把不是素数的都筛选出来
		if(!((flag[i/32]>>(i%32))&1)){
			primes[pi++] = i;
			for(int j=i; j<LEN; j+=i){
				//将第j位设置为1，表示不是素数
				flag[j/32] |= (1<<(j%32));
			}
		}
	}
	primes[0] = pi - 1;
	cout<<"count:"<<primes[0]<<endl;
	return primes;
}

 

 

7.时间复杂度分析

10万个数：这个数来测试有些小，可以大些，这样效果比较明显

时间花费依次：62ms, 15ms, 0ms, 0ms 

当然最好两个是0ms这个大些才能看出来，非常明显的效果提升

 

8.所有代码

 

/**
	*说明：
	*有一个重要的性质:任何一个合数一定可以表示成若干个素数之积。
	*如：4 = 2 * 2，6 = 2 * 3，12 = 2 * 2 * 3。也就是说，
	*合数N一定是小于N的某个（或若干）素数的整数倍,反之，如果N不是任何比它小的素数的倍数，
	*则N必然是素数。
/**
	* Author: [e-mail]
	* Data  : 2012-06-02 22:20
	* 
	*
	*/
#include <iostream>
#include <cmath>
#include <ctime>
const int LEN = 100000;
using namespace std;

//检查n是不是素数
bool isPrime(int n){
	if(n ==0 || n==1) return 0;
	for(int i=2; i<=sqrt(n); i++){
		if(n%i == 0){
			 cout<<i<<endl;
			 return 0;
		}
	}
	return 1;
}

/**
	*经典素数求解算法
	*prime[0]中保存素数总个数
	*/
int* getPrime(){
	int prime[LEN] = {0};//判断是否为素数,初始都为素数
	prime[0] = 0; //保存素数的总个数
	for(int n=2; n<LEN; n++){
		bool flag = 1;
		//对每个数A都按照：2到sqrt(A)依次除，看是否整除，如果能则不是素数
		//这样是很低效的m*m<=n也可写成m<=sqrt(n)
		//注意：必须有m*m<=n 中的“=”
		for(int m=2; m*m<=n; m++){
			//如果能整除，不是素数
			if(n%m == 0){
				flag = 0;
				break;
			}
		}
		if(flag){
			prime[0]++;
			prime[prime[0]] = n;
		}
	}
	cout<<"\ncount:"<<prime[0]<<endl;
	return prime;
}


/**
	*它是上面经典算法改进版
	*这里prime数组中存的是素数,prime[0]中保存素数总个数
	*获取0-n的所有素数
	*/
int* getPrime1(){
	int prime[LEN] = {0};//判断是否为素数,初始都为素数
	int i, n, flag;
  prime[0] = 0; //保存素数的总个数
  for (n =2 ; n < LEN; n++)
  {
        flag = 1;
        //判断当前n是否被"已经找出的素数"整除（如果能，说明不是素数,根据合数性质）
        //使用条件prime[i] * prime[i] <= n，就是判断一个数A是否是素数的时候，不需要
        //从2-A的所有数都去看是否能整除，只需要看2-sqrt(A)即可，即最终整除位置为sqrt(A),见上面isPrime(int n)
        //这里是用prime[i]去整除，故而只需要prime[i]*prime[i]<=n也可写成prime[i]<=sqrt(n)
        for (i = 1; i <= prime[0] && prime[i] * prime[i] <= n; i++)
        	//如果不是素数，break，flag=0
            if (n % prime[i] == 0)
            {
                flag = 0;
                break;
            }
        //flag=1，则说明是素数，存储
        if (flag)
        {       
            prime[0]++;//素数个数
            prime[prime[0]] = n;//将确定了的素数放入数组
        }
  }
  cout<<"\ncount:"<<prime[0]<<endl;
	return prime;
}


//------------------------------下面两个算法是典型的以空间换时间，不过空间改进即可---------------------------------------------------
/**
	*厄拉多塞筛算法:prime[0]中保存素数总个数
	*首先，将所有的数组元素设为0，表示没有已知的非素数。
	*然后将已知为非素数（即为已知素数的倍数）的索引对应的数组元素设置为1。
	*如果将所有较小素数的倍数都设置为1之后，a[i]仍然保持为0，
	*则可判断它是所找的素数。
	*/
int* getPrime2(){
	int count = 0;
	int primes[LEN / 3] = {0}, pi=1;
	int flag[LEN] = {0};//判断是否为素数,初始都为素数
	//0,1不是素数
	flag[0]=1;
	flag[1]=1;
	for(int i=2; i<LEN; i++){
		//倍数必然不是素数，把不是素数的都筛选出来
		if(!flag[i]){
			primes[pi++] = i;
			// 注意：这里只用素数来筛，因为合数筛时肯定被素数筛过了，所以没必要.
			//为什么？因为合数的性质：任何一个合数一定可以表示成若干个素数之积。如：4 = 2 * 2，6 = 2 * 3，12 = 2 * 2 * 3
			//即所有合数，都可以分解成若干个素数。
			for(int j=i; j<LEN; j+=i){
				//为什么9624会出现在素数中？
				//if(j == 9624) cout<<"-----"<<i<<" "<<j<<endl;
				flag[j]=1;
				count++;
			}
		}
	}
	//从count可以看出，对于一个位置重复访问了许多次，可以优化
	cout<<"访问数组总数："<<count<<endl;
	primes[0] = pi - 1;
	cout<<"count:"<<primes[0]<<endl;
	return primes;
}


/**
	*厄拉多塞筛算法改进版:prime[0]中保存素数总个数
	*使用一个数组来包含最简单的元素类型，0和1两个值，
	*如果我们使用位的数组，而不是使用整数的数组，则可获得更高的空间有效性
	*/
int* getPrime3(){
	int primes[LEN / 3] = {0}, pi=1; //实际素数的个数最多就是LEN / 3,故而没用LEN
	//用位替代int prime[LEN] = {0};//判断是否为素数,初始都为素数
	int flag[LEN/32] = {0};//每个int是4字节=32bit（32位）可以存储32个0,1，故而只需要LEN/32个长度的数组即可
	for(int i=2; i<LEN; i++){
		//倍数必然不是素数，把不是素数的都筛选出来
		if(!((flag[i/32]>>(i%32))&1)){
			primes[pi++] = i;
			for(int j=i; j<LEN; j+=i){
				//将第j位设置为1，表示不是素数
				flag[j/32] |= (1<<(j%32));
			}
		}
	}
	primes[0] = pi - 1;
	cout<<"count:"<<primes[0]<<endl;
	return primes;
}


int main(){
	clock_t start, finish;
  start = clock();
	int n = 0;
	/*
	cout<<"输入判断的数："<<endl;
	cin>>n;
	if(isPrime(n)){
		cout<<"是素数"<<endl;
	}else{
		cout<<"不是素数"<<endl;
	}
	*/
	
	//-------------------------方法1(经典算法62ms)----------------------------
	//getPrime();
	/*
	int *a = getPrime();
	for(int i=1; i<LEN; i++){
		if(a[i]==0) break;
		cout<<a[i]<<" ";
	}
	*/
	
	//-------------------------方法1(经典算法改进15ms)----------------------------
	//getPrime1();
	/*
	int *a = getPrime1();
	for(int i=1; i<LEN; i++){
		if(a[i]==0) break;
		cout<<a[i]<<" ";
	}
	*/
	
	//----------------------------方法3(厄拉多塞筛算法<1ms)----------------------------
	//getPrime2();
	/*
	int *a = getPrime2();
	for(int i=1; i<LEN; i++){
		if(a[i]==0) break;
		cout<<a[i]<<" ";
	}
	*/
	
	//----------------------------方法3(厄拉多塞筛算法改进<1ms)----------------------------
	//getPrime3();
	
	int *a = getPrime3();
	for(int i=1; i<LEN; i++){
		if(a[i]==0) break;
		cout<<a[i]<<" ";
	}
	
	
  finish = clock();
  cout<< "\nCost Time: " << finish - start << " ms";
	return 0;
}