筛法求素数

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

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

# author: jtusta # contact: root@jtahstu.com # site: http://www.jtahstu.com # software: RubyMine # time: 2017/6/7 15:41 class Prime @@array = Array.new 105,1 def initialize(n=100) @n = n end # 筛法求素数,乘法 def do for i in 2..@n for j in 2..@n/i @@array[i*j]=0 end end end # 筛法求素数,加法 def do_2 for i in 2..@n-1 @@array[i] = i%2==0?0:1 end @@array[2]=1 # 特别的2是素数 i = 3 while i<=Math.sqrt(@n) if @@array[i]==1 j = i+i while j<@n @@array[j]=0 j+=i end end i+=2 end end # 输出数组 def put for i in 2..@n if @@array[i]==1 print i,' ' end end puts end end prime = Prime.new prime.do prime.put prime2 = Prime.new prime2.do_2 prime2.put

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

#define MAX_N 1000 int a[MAX_N+1]; int p[MAX_N+1]; int nCount=0; void Init(int n) //线性筛法，不过在小范围上(约n<1e7)不比上一个方法快 { for (int i=2;i<=n;i++) { if (a[i]==0) { p[++nCount]=i; } for (int j=1,k; (j<=nCount) && (k=i*p[j])<=n; j++) //筛选循环 { a[k] = 1 ; if (i%p[j] == 0) break; } } } #include <iostream> int main(void) { Init(MAX_N); for(int n=1; p[n]>1; ++n) { printf("]", p[n]); } return 0; }

素数相关知识

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

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

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