算法与数据结构求质数总结

       质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
一、判断一个数是否为质数

       首先根据定义，最简单的判断一个数n是否为质数的方法，就是从2开始对小于n的所有数，依次判断是否能整除n，若都不能整除就是质数。

1. bool IsPrime(int n)  
2. {  
3.     if(n == 1)  
4.         return false;  
5.     for(int i = 2; i < n; i++)  
6.         if(n % i ==0)  
7.             return false;  
8.     return true;  
9. }  

        我们再稍微改进一下，我们可以先判断一下2能不能整除n，然后2以上的偶数就不需要再判断了，因为2不能整除n那么含有因子2的数肯定也不能整除n。再者，我们根本不需要循环到n，若两个数的乘积为n，那么肯定有一个因子是小于sqrt(n)的，所以，循环的上限可以取sqrt(n)。于是就有：

1. bool IsPrime(int n)  
2. {  
3.     if(n == 2)  
4.         return true;  
5.     if(n == 1 || (n & 1))  
6.         return false;  
7.     int k = (int)sqrt(n);  
8.     for(int i = 3; i <= k; i += 2)  
9.         if(n % i == 0)  
10.             return false;  
11.     return true;  
12. }  

       上面是过滤掉了2的倍数，计算量变为原来的二分之一，我们也可以把3的倍数过滤掉，也就是只判断3是否能整除n，其它3的倍数就不需要判断了，计算量就可以变为原来的三分之一。也就是只剩6*k+1和6*k+5（k为整数）这些数，因为其他数都含有因子2或3，n若不能被2或3整除，那么n也不能被6*k，6*k+2，6*k+3，6*k+4这些数整除，就不需要判断这些数能否整除n了，这样又减少了判断量。

1. bool IsPrime(int n)  
2. {  
3.     if((n == 2) || (n == 3))  
4.         return true;  
5.     if((n == 1) || ((n & 1) == 0) || ((n % 3) ==0))  
6.         return false;  
7.     int k = (int)sqrt(n);  
8.     int step = 4;  
9.     for(int i = 5; i <= k; i += step)  
10.     {  
11.         if(n % i == 0)  
12.             return false;  
13.         step = 6 - step;  
14.     }  
15.     return true;  
16. }  

二、找出区间内的所有质数

       要求区间内的所有质数，首先可以用以上判断单个质数的方法挨个寻找，但是太慢了。。。
       这类问题主要的就是筛选法了。筛法求质数的主要思想就是，从小到大，当判断完一个数K是否为质数后，把后面的所有的K的倍数（含因子K）都去掉。

1. #define N 1000000   
2. bool isPrime[N];  
3. int i;  
4. memset(isPrime, true, sizeof(isPrime));  
5. isPrime = false;  
6. //筛掉大于2的偶数   
7. for(i = 4; i < N; i += 2)       
8.     isPrime[i] = false;    
9. int bound = sqrt(N);    
10. //用sqrt(N)以内的质数去筛掉后面含有质数因子的元素     
11. for(i = 3; i <= bound; i += 2)                 
12. {  
13.     //从3开始的奇数，如果是质数就去筛掉以自己为因子的元素，不是质数跳过   
14.     if(false == isPrime[i])   
15.         continue;    
16.     int step = i << 1;     
17.     //i为质数，则从i*i开始筛，以2*i为步长（因为偶数已被筛掉，小于i*i的非质数，已被小于i的质数筛掉）   
18.     for(int j = i * i ; j < N ; j += step) //含有质数因子i，筛掉         
19.         isPrime[j] = false;              
20. }  

       若求两个大数之间的质数，也可以用筛法
       如求N1和N2之间的质数1000000000 <= N1 < N2 < 2^32 and 1 < N2 - N1 < 1000000bool isPrime[1000000];  

1. int prime[70000]; //保存小于65536的质数（可以筛unsigned int范围内的数），筛法求出   
2. int primeCnt;     //小于65536的质数个数   
3. int i, j;  
4. /* 
5. 求小于65536的质数，保存在prime数组中 
6. */  
7. int N1 = 100000000;  
8. int N2 = 101000000;  
9. scanf("%d%d", &n1, &n2);  
10. int D = N2 - N1;  
11. memset(isPrime, true, sizeof(isPrime));  
12. for(i = 0; i < primeCnt; i++)  
13. {   
14.     int k = N2 % prime[i];   
15.     //可知 N2-k 含质因子prime[i]，不是质数，N2 - k - x*prime[i]（x为整数）都不是质数数，筛掉     
16.     int step = prime[i];   
17.     int j = D - k;   
18.     // N2 - k 对应于数组下标 D - k, N2 - k - x * prime[i] 对应于数组下标 j - x * prime[i];    
19.     while(j >= 0)   
20.     {  
21.         isPrime[j] = false; //isPrime[j] 代表 N1 + j 是否是质数   
22.         j -= step;   
23.     }  
24. }  

TAG: java算法

点击下载系统：http://www.myeducs.cn/chaxun/index.html?go=算法与数据结构求质数总结&aa=%CB%D1%CB%F7%C2%DB%CE%C4