[关闭]
@jtahstu 2017-06-07T08:55:32.000000Z 字数 1557 阅读 223

筛法求素数

算法


用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。 --来自百度百科

代码中介绍了两种写法,查阅资料时有看到其他的写法,这里主要关注思想,效率还有待优化,这两种写法效率都不怎样,是有更好的写法的,那就自行Google吧。

  1. # author: jtusta
  2. # contact: root@jtahstu.com
  3. # site: http://www.jtahstu.com
  4. # software: RubyMine
  5. # time: 2017/6/7 15:41
  6. class Prime
  7. @@array = Array.new 105,1
  8. def initialize(n=100)
  9. @n = n
  10. end
  11. # 筛法求素数,乘法
  12. def do
  13. for i in 2..@n
  14. for j in 2..@n/i
  15. @@array[i*j]=0
  16. end
  17. end
  18. end
  19. # 筛法求素数,加法
  20. def do_2
  21. for i in 2..@n-1
  22. @@array[i] = i%2==0?0:1
  23. end
  24. @@array[2]=1 # 特别的2是素数
  25. i = 3
  26. while i<=Math.sqrt(@n)
  27. if @@array[i]==1
  28. j = i+i
  29. while j<@n
  30. @@array[j]=0
  31. j+=i
  32. end
  33. end
  34. i+=2
  35. end
  36. end
  37. # 输出数组
  38. def put
  39. for i in 2..@n
  40. if @@array[i]==1
  41. print i,' '
  42. end
  43. end
  44. puts
  45. end
  46. end
  47. prime = Prime.new
  48. prime.do
  49. prime.put
  50. prime2 = Prime.new
  51. prime2.do_2
  52. prime2.put

各种变形中的一种,自己理解吧

  1. #define MAX_N 1000
  2. int a[MAX_N+1];
  3. int p[MAX_N+1];
  4. int nCount=0;
  5. void Init(int n) //线性筛法,不过在小范围上(约n<1e7)不比上一个方法快
  6. {
  7. for (int i=2;i<=n;i++)
  8. {
  9. if (a[i]==0)
  10. {
  11. p[++nCount]=i;
  12. }
  13. for (int j=1,k; (j<=nCount) && (k=i*p[j])<=n; j++) //筛选循环
  14. {
  15. a[k] = 1 ;
  16. if (i%p[j] == 0) break;
  17. }
  18. }
  19. }
  20. #include <iostream>
  21. int main(void)
  22. {
  23. Init(MAX_N);
  24. for(int n=1; p[n]>1; ++n)
  25. {
  26. printf("%5d", p[n]);
  27. }
  28. return 0;
  29. }

素数相关知识

最大公约数只有1和它本身的数叫做质数(素数)——这个应该知道吧?-_-b

至今为止,没有任何人发现素数的分布规律,也没有人能用一个公式计算出所有的素数。关于素数的很多的有趣的性质或者科学家的努力。

  1. 高斯猜测,n以内的素数个数大约与n/ln(n)相当,或者说,当n很大时,两者数量级相同。这就是著名的素数定理。  
  2. 十七世纪费马猜测,2的2^n次方+1,n=0,1,2…时是素数,这样的数叫费马素数,可惜当n=5时,2^32+1就不是素数,至今也没有找到第六个费马素数。
  3. 18世纪发现的最大素数是2^31-1,19世纪发现的最大素数是2^127-1,20世纪末人类已知的最大素数是2^859433-1,用十进制表示,这是一个258715位的数字。
  4. 孪生素数猜想:差为2的素数有无穷多对。目前知道的最大的孪生素数是1159142985×2^2304-1和1159142985×2^2304+1。
  5. 歌德巴赫猜想:大于2的所有偶数均是两个素数的和,大于5的所有奇数均是三个素数之和。其中第二个猜想是第一个的自然推论,因此歌德巴赫猜想又被称为1+1问题。我国数学家陈景润证明了1+2,即所有大于2的偶数都是一个素数和只有两个素数因数的合数的和。国际上称为陈氏定理。
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注