转自梦醒潇湘       http://blog.chinaunix.net/uid-26548237-id-3364131.html

先收藏起来，往后慢慢研究。。

*****************************************以下为正文******************************************************

  今天，关于素数问题纠结了好久好久，倍感知识缺乏啊。因此，通过自己的了解和网上查阅资料，加上自己的啰嗦，在这里整理一下，日后可以翻阅。

   首先，感谢网上的前辈，如果没有您们，我不会获得关于素数的比较全面的知识。非常感谢。

  

1、素数及相关

   素数，又称质数，在一个大于1的自然数中，除了1和此整数自身之外，不能被其他自然数整除的数。

   比1大但不是素数的数称为合数。

   1和0既不是素数，也不是合数。

   算术基本定理证明每个大于1的正整数都可以写成素数的乘积，并且这种乘积的形式是唯一的。

2、试除法求素数

   算法描述：根据素数的定义可知，不能被1和自身外的整数整除的数为素数。所以，我们可以得知，判断一个素数是否为素数只要看它是否能被2~sqrt(i)间的数整数即可。而求N内所有素数则是循环重复上述过程。

 

   C语言实现如下所示。

1. #include <stdio.h>

2. #include <time.h>

3. #include <math.h>

4. #include <malloc.h>

5. //试除法

6. #define NUM 10000

8. int Test_prime(int n)

9. {

10.     int count = 0;

11.     int i, j;

12.     int *num= (int*)malloc(sizeof(int)* n);

13.     num[count++]= 2;

14.     

15.     for(i = 3; i <= n; i++)

16.     {

17.         for(j= 2; j <= sqrt(i); j++)

18.         {

19.             if(i% j == 0)

20.             {

21.                 break;

22.             }

23.         }

24.         if(j> sqrt(i))

25.         {

26.             num[count++]= i;

27.         }

28.     }

29.     free(num);

30.     return count;

31. }

32. int main()

33. {

34.     int count;

35.     clock_t start,end;

36.     start = clock();

37.     count = Test_prime(NUM);

38.     end = clock();

39.     printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);

41.     return 0;

42. }

   测试结果如下所示（测试在VC6.0下进行）。

  从上面可以看出，当数据很大时，时间消耗增长的比较快。

3、试除法的优化方案

  

   仔细研究试除法，可以发现以下几个问题：

   1> 在循环条件中重复调用了sqrt(i)，这显然是比较浪费时间的；

   2> 判断素数，真的需要拿2-sqrt(i)间的所有整数去除吗？我们知道，合数都可以分解成若干质数，所以，只要2-sqrt(i)间的质数不能整除i即可；

   C语言实现如下所示。

点击(此处)折叠或打开

1. //求N内的所有素数

2. #include <stdio.h>

3. #include <time.h>

4. #include <math.h>

5. #include <malloc.h>

6. //试除法

7. #define NUM 1000000

9. int Test_prime(int n)

10. {

11.     int count = 0;

12.     int i, j, k, stop;

13.     //分配空间

14.     int *num= (int*)malloc(sizeof(int)* n);

15.     //2肯定是素数

16.     num[count++]= 2;

17.     stop = 0;

18.     for(i = 3; i <= n; i++)

19.     {

20.         //在循环中重复调用sqrt是低效做法，故引入k

21.         k = (int)sqrt(i);

22.         //stop的作用是：统计小于当前k值的质数的数目

23.         while(num[stop]<= k && stop < count)

24.         {

25.             stop++;

26.         }

27.         for(j= 0; j < stop; j++)

28.         {

29.             if( i% num[j]== 0)

30.             {

31.                 //i不能被2-sqrt(i)间的素数整除，自然不能被其他整数整除，所以为素数

32.                 break;

33.             }

34.         }

35.         if(j== stop)

36.         {

37.             num[count++]= i;

38.         }

39.        

40.     }

41.     free(num);

42.     return count;

43. }

44. int main()

45. {

46.     int count;

47.     clock_t start,end;

48.     start = clock();

49.     count = Test_prime(NUM);

50.     end = clock();

51.     printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);

52.    

53.     return 0;

54. }

  测试结果如下所示。

   相对于优化前的算法，时间提供了很多。特别是在时间增长曲线的幅度变小了，N值越大，优化后的算法比优化后的算法效率更高。

4、合数过滤筛选法

   算法描述：由质数的定义可以知道，质数N不能被2-（N-1）间的任何整数整除；反过来看，只要能被2-（N-1)间的任何整数整除的N，都不是素数。所以，我们采用排除法：就是对N以内的所有数，只要逐个 去除 值为2-（N-1)的倍数的数，剩下的就是素数。

   C语言实现如下所示。

1. //合并筛选法

2. #include <stdio.h>

3. #include <time.h>

4. #include <math.h>

5. #include <malloc.h>

6. //试除法

7. #define NUM 10000

9. int Test_prime(int n)

10. {

11.     int count = 0;

12.     int i, j;

13.     //分配空间，之所以是n+1，是因为浪费了一个num[0]

14.     char *num =(char *)malloc(sizeof(char)* (n + 1));

16.     //初始化素数标记

17.     for(i = 2; i<= n; i++)

18.     {

19.         num[i]= 1;

20.     }

21.     //以2-(N-1)为因子过滤合数

22.     for(i = 2; i <= n-1; i++)

23.     {

24.         for(j= 2; j * i <= n; j++)

25.         {

26.             //i*j是由两整数相乘而得，显然不是素数

27.             num[i*j]= 0;

28.         }

29.     }

30.     //统计素数个数

31.     for( i = 2; i<= n; i++)

32.     {

33.         if( 1== num[i])

34.         {

35.             count++;

36.         }

37.     }

38.     free(num);

39.     return count;

40. }

41. int main()

42. {

43.     int count;

44.     clock_t start,end;

45.     start = clock();

46.     count = Test_prime(NUM);

47.     end = clock();

48.     printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);

49.    

50.     return 0;

51. }

   测试结果如下所示。

   上述程序好多地方采用了比较低效的做法，为了与后文的优化作比较，这也是像我一样的初学者通常采用的版本，因此，要学会优化。

5、合并筛选法优化方案

   上述算法存在的问题是：

   1> 在外层循环，需要一直执行到n-1嘛？不要，因为n/2-（n-1）之间的数显然不能整除出n；

   2> 在内层循环中重复使用i*j显然是低效的，考虑到计算机中加减运算速度比乘除快，可以考虑变乘法为加法；

   3> 在循环修改flag的过程中，其实有很多数被重复计算若干次，比如6 = 2*3 = 3*2,被重复置零，所以，可以进行避免；

  

   C语言实现如下所示。

点击(此处)折叠或打开

1. //合并筛选法的优化方案

2. #include <stdio.h>

3. #include <time.h>

4. #include <math.h>

5. #include <malloc.h>

7. #define NUM 300000

9. int Test_prime(int n)

10. {

11.     int count = 0;

12.     int i, j;

13.     //分配空间

14.     char *num =(char *)malloc(sizeof(char)* (n + 1));

15.    

16.     //初始化素数标记

17.     num[2] = 1;

18.     //注意此处是i<n，上例中的i<=n

19.     for(i = 3; i< n; i++)

20.     {

21.         num[i++]= 1;

22.         num[i]= 0;//偶数自然不是素数

23.     }

24.     //如果n为奇数

25.     if(n % 2 != 0)

26.     {

27.         num[n]= 1;

28.     }

29.     //从3开始过滤，因为，2的倍数在初始化中去掉了

30.    for(i = 3; i <= n/2; i++)

31. **    {**

32. **        if(0 == num[i] )**

33. **        {**

34. **            continue;**

35. **        }**

36. **        //从i的2倍开始过滤**

37. **        for(j = i + i; j <= n;j+=i)**

38. **        {**

39. **            num[j] = 0;**

40. **        }**

41. **    }**

42.     //统计素数个数

43.     for( i = 2; i<= n; i++)

44.     {

45.         if( 1== num[i])

46.         {

47.             count++;

48.         }

49.     }

50.     free(num);

51.     return count;

52. }

53. int main()

54. {

55.     int count;

56.     clock_t start,end;

57.     start = clock();

58.     count = Test_prime(NUM);

59.     end = clock();

60.     printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);

61.    

62.     return 0;

63. }

   测试如下所示。

  确实比先前快了很多，优化真的可以带来时间的提高，这样我很是欣喜。

  

   后来想到进行添加补充：

 

   如果我对上述红色部分代码进行优化，如下所示。

点击(此处)折叠或打开

1. //从3开始过滤，因为，2的倍数在初始化中去掉了

2.     for(i = 3; i <= n/2;i = i + 2)

3.     {

4.         //在这里进行判断，就已经具有剔除了偶数的功能

5.         if(0== num[i])

6.         {

7.             continue;

8.         }

9.         //从i的2倍开始过滤

10.         for(j= i + i; j<= n;j+=i)

11.         {

12.             //是直接进行赋值快呢？还是在此处加上判断快呢？？不晓得啊？求解。。

13.            if( j % 2 == 0)

14.             {

15.                 continue;

16.             }

17.             else

18.             {

19.                 num[j]= 0;

20.             }

21.         }

22.     }

   第一部分红色，我将原来的奇数和偶数进行判断，变为了只对奇数进行判断；

   第二部分红色，我将奇数的倍数为偶数的直接剔除，变成只对倍数为奇数的进行赋值；

   以上两者改变，都基于开始时，已经将偶数剔除。

   对NUM = 300000测试如下所示。

  

   时间仅为7毫秒，比 优化前NUM = 300000时，时间更快。

6、继续优化

  

   C语言实现代码如下所示。

点击(此处)折叠或打开

1. //合并筛选法的优化方案

2. #include <stdio.h>

3. #include <time.h>

4. #include <math.h>

5. #include <malloc.h>

6. #include <string.h>

7. #define NUM 10000

9. int Test_prime(int n)

10. {

11.     int i, j;

12.     // 素数数量统计

13.     int count = 0;

14.     // 分配素数标记空间，明白+1原因了吧，因为浪费了一个num[0]

15.     char *num =(char*)malloc( n+1);

16.     // 干嘛用的，请仔细研究下文

17.     int mpLen = 2*3*5*7*11*13;

18.     char magicPattern[2*3*5*7*11*13];

19.     // 奇怪的代码，想！

20.     for (i=0; i<mpLen; i++)

21.     {

22.         magicPattern[i++]= 1;

23.         magicPattern[i++]= 0;

24.         magicPattern[i++]= 0;

25.         magicPattern[i++]= 0;

26.         magicPattern[i++]= 1;

27.         magicPattern[i]= 0;

28.     }

29.     for (i=4; i<=mpLen; i+=5)

30.     {

31.         magicPattern[i]= 0;

32.     }

33.     for (i=6; i<=mpLen; i+=7)

34.     {

35.         magicPattern[i]= 0;

36.     }

37.     for (i=10; i<=mpLen; i+=11)

38.     {

39.         magicPattern[i]= 0;

40.     }

41.     for (i=12; i<=mpLen; i+=13)

42.     {

43.         magicPattern[i]= 0;

44.     }

45.    

46.     // 新的初始化方法,将2,3,5,7,11,13的倍数全干掉

47.     // 而且采用memcpy以mpLen长的magicPattern来批量处理

48.     int remainder = n%mpLen;

49.     char* p = num+1;

50.     char* pstop = p+n-remainder;

51.     while (p< pstop)

52.     {

53.         memcpy(p, magicPattern, mpLen);

54.         p += mpLen;

55.     }

56.     if (remainder> 0)

57.     {

58.         memcpy(p, magicPattern, remainder);

59.     }

60.     num[2] = 1;

61.     num[3] = 1;

62.     num[5] = 1;

63.     num[7] = 1;

64.     num[11]= 1;

65.     num[13]= 1;

66.    

67.     // 从17开始过滤，因为2,3,5,7,11,13的倍数早被去掉了

68.     // 到n/13止的

69.     int stop = n/13;

70.     for (i=17; i<= stop; i++)

71.     {

72.         // i是合数

73.         if (0== num[i])

74.         {

75.             continue;

76.         }

77.        

78.         // 从i的17倍开始过滤

79.         int step= i*2;

80.         for (j=i*17; j<= n; j+=step)

81.         {

82.             num[j]= 0;

83.         }

84.     }

85.    

86.     // 统计素数个数

87.     for (i=2; i<=n; i++)

88.     {

89.         if (num[i])

90.         {

91.             count++;

92.         }

93.     }

94.    

95.     // 释放内存

96.     free(num);

97.    

98.     return count;

99. }

100. int main()

101. {

102.     int count;

103.     clock_t start,end;

104.     start = clock();

105.     count = Test_prime(NUM);

106.     end = clock();

107.     printf("%d 内的素数个数为：%d, 总共耗时为：%d 毫秒\n", NUM, count,end - start);

108.    

109.     return 0;

110. }

   测试结果如下所示。

**  ** 说实话，这种思想真的很赞，现在的我是无法想到的，感谢作者，让我有了更广泛的见识。

7、其他

   除了以上几种算法外，如拉宾米勒素数测试算法，感觉这个算法比较难，先好好看看，等弄懂了，然后补上。

  

   通过今天的纠结，对于求素数有了更加深刻的了解和认识，感觉自己还差很多，需要更加的努力。

   另外，感谢来自百度空间的作者 doforfun_net，给我了很大的启发，学到了很多。

                                                      梦醒潇湘

                                                  2012-10-3 20:15

 

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/8066111