用筛法求素数
输出素数表，方法之一就是舍弃空间，换取时间，也就是用一个大数组来存放每一个数是不是素数。这样用筛法求素，大大的减少了时间。下面的筛法求素程序求（不输出，即不定义OUT）1亿以内的素数只需要十几秒的时间，远小于输出所需的时间。
这个程序用一个char数组来存放每一个奇数是不是素数的信息。一个char是一个字节8位，存放8个数。
Program prime_char.cpp:
#include
#include
#include
//#define DEBUG
#define OUT
using namespace std;
//常量定义
const long MAX=100000000;
const long CHAR_MAX=int(MAX/16+1);
const char byt[8]={128,64,32,16,8,4,2,1};
// 变量定义
/**********************************
prime saves whether n is a prime
the value of n is like:
prime[0]: 3, 5, 7, 9,11,13,15,17
prime[1]:19,21,23,25,27,29,31,33
**********************************/
unsigned char prime[CHAR_MAX];
// 函数声明
inline bool isprime(long);
inline void setcomposite(long);
void primeinitiate(void);
void out(long);
//函数定义
/****************************************
*Function main *
****************************************/
int main()
{
#ifdef DEBUG
test();
#else
long n,m;
primeinitiate();
n=5;
while(n*n<=MAX)
{
if (isprime(n))
{
#ifdef OUT
out(n);
#endif
m=int(MAX/n);
if (m%2==0) m--;
while(m>=n)
{
if (isprime(m)) setcomposite((m*n)); m-=2;
}
}
n+=2;
}
#ifdef OUT
for (;n<=MAX;n+=2)
{
if (isprime(n))
out(n);
}
#endif
#endif
cout << "OK";
getch();
return 0;
}
/****************************************
*Test function *
****************************************/ void test(void)
{
}
/****************************************
*Function primeinitiate *
*to initiate the array prime[] *
*input : nothing *
*output : nothing *
****************************************/ void primeinitiate(void)
{
long i;
for(i=0;i { if (i==0) prime[i]=237; //11101101 else if(i%3==0) prime[i]=109; //01101101 else if(i%3==1) prime[i]=182; //10110110 else if(i%3==2) prime[i]=219; //11011011 } } /**************************************** *Function isprime * *To know if we haven't been sure that * * n is a composite * *Input : n * *Output : false if we are sure that n * * is a composite; * * ture if we aren't sure that n* * is a composite; * ****************************************/ inline bool isprime(long n) { return ((prime[int((n-3)/16)] & byt[((n-3)%16)/2]) != 0); } /**************************************** *Function setcomposite * *To let us be sure that an integer is * *a prime * *Input : n * *Output : nothing * ****************************************/ inline void setcomposite(long n) { prime[int((n-3)/16)] &= ~byt[((n-3)%16)/2]; // return UNCHECKED; } void out(long n) { static long i=0; cout << setw(5) << setiosflags(ios::right)<< n << " "; i++; i%=100; if (i%10==0) cout << endl; if (i%100==0) getch(); } (以上程序经过Dev-C++ 4.9.6.0编译通过) 很久以前编的程序，现在拿出来见见天日吧。 我发现了筛法的计算公式 孟庆馀［江苏连云港］ 2010年5月 [摘要]： 笔者在探索中，发现了有关素数与合数关系的三条主要规律： １、区段（区域）性的规律。 ２、逐项相除四舍五入的规律。 ３、随从数的规律。 根据这三条规律推导出一个公式, 它可以计算出任一已知素数后边紧跟的那个素数和任意大的一个自然数之前共有多少个素数的问题。 这个公式是： m p = 2N -N [ (211p p +311p p -3211p p p ±…±13211-n p p p p Λ)+ （ )1111132131211-±±++-n p p p p p p p p p ΛΛ（-n p 1）]+（1-n ） [关键词]： 筛法公式、逐项相除、四舍五入、区段、随从数。 [正文]： 笔者在多年的探索中，发现了有关素数与合数关系的一些规律，根据这些规律找到了一个可以对埃拉多斯染尼氏（Eratosthenes ）筛法进行计算的公式，即“筛法计算公式”(它包括计算素数和计算奇合数两个公式)，计算素数的公式也可以称为“素数公式"。给素数找出一个通项表达式，即已知任一素数后边紧跟的那个素数的公式，这是一个缠绕着数学家的世界难题，时至今日都没有解决。笔者的这个公式能较好地解决任一已知素数后边紧跟的那个素数的问题。 一、“筛法计算公式”(用于计算素数) m p = 2N -N [ (211p p +311p p -3211p p p ±…±13211-n p p p p Λ)+ （)1111132131211-±±++-n p p p p p p p p p ΛΛ（-n p 1）]+（1-n ） …（1） 式中m p 为1~N 数列中素数个数；N 为任意大的自然数（2n p ≤N <21+n p ） ；n p p p p ,,,,321K 为素数，其中：1p = 2，2p = 3，3p = 5，…,6p = 13，…；n ≥2 。 试编写一个程序，找出2->N之间的所有质数。希望用尽可能快的方法实现。 【问题分析】： 这个问题可以有两种解法：一种是用“筛子法”，另一种是从2->N检查，找出质数。 先来简单介绍一下“筛法”，求2~20的质数，它的做法是先把2~20这些数一字排开： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 先取出数组中最小的数，是2，则判断2是质数，把后面2的倍数全部删掉。 2 | 3 5 7 9 11 13 15 17 19 接下来的最小数是3，取出，再删掉3的倍数 2 3 | 5 7 11 13 17 19 一直这样下去，直到结束。 筛法求质数的问题时，非质数的数据有很多是重复的。例如，如果有一个数3×7×17×23，那么在删除3的倍数时会删到它，删7、17、23时同样也会删到它。有一种“线性筛法”，可以安排删除的次序，使得每一个非质数都只被删除一次。从而提高效率。因为“筛法”不是我要介绍的重点，所以就不介绍了。 现在我来介绍第二种方法。用这种方法，最先想到的就是让从2~N逐一检查。如果是就显示出来，如果不是，就检查下一个。这是正确的做法，但效率却不高。当然，2是质数，那么2的倍数就不是质数，如果令i从2到N，就很冤枉地测试了4、6、8……这些数？所以第一点改建就是只测试2与所有的奇数就足够了。同理，3是质数，但6、9、12……这些3的倍数却不是，因此，如果能够把2与3的倍数跳过去而不测试，任意连续的6个数中，就只会测试2个而已。以6n,6n+1,6n+2,6n+3,6n+4,6n+5为例，6n,6n+2,6n+4是偶数，又6n+3是3的倍数，所以如果2与3的倍数都不理会，只要测试的数就只留下6n+1和6n+5而已了，因而工作量只是前面想法的2/6=1/3，应该用这个方法编程。 还有个问题，就是如果判断一个数i是否为素数。按素数的定义，也就是只有1与本身可以整除，所以可以用2~i-1去除i，如果都除不尽，i就是素数。观点对，但却与上一点一样的笨拙。当i>2时，有哪一个数可以被i-1除尽的？没有，为什么？如果i不是质数，那么i=a×b，此地a与b既不是i又不是1；正因为a>1，a至少为2，因此b最多也是i/2而已，去除i的数用不着是2~i-1，而用2~i/2就可以了。不但如此，因为i=a×b，a与b不能大于sqrt(i),为什么呢？如果a>sqrt(i),b>sqrt(i),于是a×b>sqrt(i)*sqrt(i)=i，因此就都不能整除i了。如果i不是质数，它的因子最大就是sqrt(i)；换言之，用2~sqrt(i)去检验就行了。 但是，用2~sqrt(i)去检验也是浪费。就像前面一样，2除不尽，2的倍数也除不尽；同理，3除不尽，3的倍数也除不尽……最理想的方法就是用质数去除i。 但问题是这些素数从何而来？这比较简单，可以准备一个数组prime[]，用来存放找到的素数，一开始它里面有2、3、5。检查的时候，就用prime[]中小于sqrt(i)的数去除i即可，如果都除不尽，i就是素数，把它放如prime[]中，因此prime[]中的素数会越来越多，直到满足个数为止！ 不妨用这段说明来编写这个程序，但是程序设计的时候会有两个小问题： 1.如果只检查6n+1和6n+5？不难发现，它们的距离是4、2、4、2……所以，可以先定义一个变量gab=4，然后gab=6-gab; 2.比较是不能用sqrt(i)，因为它不精确。举个例子，i=121，在数学上，sqrt(i)自然是11，但计算机里的结果可能是10.9999999，于是去除的数就是2、3、5、7，而不含11，因此121就变成质数了。解决这个问题的方法很简单，不要用开方，用平方即可。例如，如果p*p<=i，则就用p去除i。而且它的效率比开方高。 【程序清单】： #include 素数普遍公式 目录[隐藏] 一、引言 二、素数普遍公式 三、素数的个数 四、公式的用途 五、素数普遍公式在认识形成中的作用和意义 思考题 一、引言 二、素数普遍公式 三、素数的个数 四、公式的用途 五、素数普遍公式在认识形成中的作用和意义 思考题 [编辑本段] 一、引言 2000多年前欧几里德在证明素数无穷多时就埋下了寻求素数普遍公式的伏笔 素数普遍公式 ，以布劳维尔为首的直觉主义学派认为：“你没有给出第n个素数是如何构造的，就不能算是好的证明”。2000多年来，数论学最重要的一个任务，就是寻找素数普遍公式，为此，一代又一代数学精英，耗费了巨大的心血，始终未获成功。黎曼曾想用他的ζ函数数的“零点”来逼近素数普遍公式，至今未获成功。也有人反向思考，用素数普遍公式逼近“零点”来解决黎曼猜想。希尔伯特在1900年的国际数学家大会上说：对黎曼公式进行了彻底讨论之后，或许就能够严格解决哥德巴赫问题和孪生素数问题。实际在哲学上，只要有一个明确的定义，就应该有一个公式。 [编辑本段] 二、素数普遍公式 公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法： （一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。 （二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1 孪生素数个数计算公式 李联忠 （营山中学 四川营山 637700） 摘要：孪生素数个数计算公式 ∑ -∑-∑-? ??? ????++ +??? ? ?? ???++??? ? ? ? ??++ =≠==p p p x p p x p x L i i i i j k j k j k kj i k k k I n n n n 2 112,12 11 )1() 1() 1(、 ＋ｑ-h n 前的素数均是n 的约数时，孪生素数个数计算公式 p p p p p p i i n L 22 12 2 1 1 -? ?-?-? = +q-h 关键词：数论 孪生素数 公式 中图分类号： 文献标识号： 文章编号： 孪生素数：相差２的素数叫孪生素数。 引理：若 p p n i 21 i 2+≤＜ ， p p p p p i i k 1 2 1 ,, ,, ,3, 2+== 为连续素数，则在1、2、 3…n 中去掉 p k 的倍数，余下的数（1除外）全为素数。 分析下面相差2的数组 （１，３） （２，４）…（ｍ，ｍ＋２）…（ｎ，ｎ＋２） (1≤m ≤n) 若 p p n i 21 i 2+≤＜ p p p p p i i k 1 2 1 ,, ,, ,3, 2+== 为连续素数，在1、2、3…n 中去 掉除以 p k 余0和余（ 2-p k ）的数，则余下的数组（ｍ，ｍ＋２）中，ｍ和（ｍ＋２） 都不是前ｉ个素数的倍数，据引理，余下的数组全为孪生素数（若n 为素数，n+2=p i 21 +， （n,n+2）除外，i=1，（1，3）除外），仿照素数公式可得出类似的孪生素数计算公式 ∑ -∑ -∑ ∑ + + ++ + + + + - =≠≠=≠==］ ［］［ ］［ ］［p p p x p p p x p p x p x L i i i i j k l j k l j k l lkj i j k j k j k kj i k k k i n n n n n 2 1 12,1,,3 ,1,1 ) 1() 1( =q-h ) )2,(),3,1(2101(该去而未去指或、倍数被去掉了；作为的孪生素数，因为它们 表不大于 +=n n h q p i ()(mod 20,),(mod 20);(mod 02 2 1 1p x p x p x i i 或或≡≡≡ 筛法求素数 目录 基本思想 C语言实现 pascal实现: 1C++实现: 2python 实现: 基本思想 用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列，1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是： 3 5 7 9 11 13 15 17 19 21 23 25 27 29 剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为： 2 3 5 7 11 13 17 19 23 29 C语言实现 1、算法一：令A为素数，则A*N（N>1;N为自然数）都不是素数。 #define range 2000 bool IsPrime[range+1]; //set函数确定i是否为素数，结果储存在IsPrime[i]中，此函数在DEV C++中测试通过 void set(bool IsPrime[]) { int i,j; for(i=0;i<=range;++i) IsPrime[i]=true; IsPrime[0]=IsPrime[1]=false; for(i=2;i<=range;++i) { if(IsPrime[i]) { for(j=2*i;j<=range;j+=i) IsPrime[j]=false; } } } 2、 说明：解决这个问题的诀窍是如何安排删除的次序，使得每一个非质数都只被删除一次。中学时学过一个因式分解定理，他说任何一个非质（合）数都可以分解成质数的连乘积。例如，16=4^2，18=2 * 3^2，691488=2^5 * 3^2 * 7^4等。如果把因式分解中最小质数写在最左边，有16=4^2，18=2*9,691488=2^5 * 21609,；换句话说，把合数N写成N=p^k * q，此时q当然是大于p的，因为p是因式分解中最小的质数。由于因式分解的唯一性，任何一个合数N，写成N=p^k * q;的方式也是唯一的。由于q>=p的关系，因此在删除非质数时，如果已知p是质数，可以先删除P^2,p^3,p^4,... ，再删除pq,p^2*q,p^3*q,...,（q是比p大而没有被删除的数），一直到pq>N为止。 因为每个非质数都只被删除一次，可想而知，这个程序的速度一定相当快。依据Gries与Misra的文章，线性的时间，也就是与N成正比的时间就足够了（此时要找出2N的质数）。（摘自《C语言名题精选百则（技巧篇）》，冼镜光编著，机械工业出版社，2005年7月第一版第一次印刷）。代码如下： #include 例6、用筛法求出100以内的全部素数，并按每行五个数显示。 【问题分析】 ⑴把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）； ⑵在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）； ⑶从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置0； ⑷让p=p+1，重复执行第②、③步骤，直到minp>Trunc(sqrt(N)) 为止； ⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。 用筛法求素数的过程示意如下（图中用下划线作删去标志）： ① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 ｛置数｝ ② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被2整除的数} ③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被3整除的数} …… 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100 {筛去被整除的数} Program Exam53; const N=100; type xx=1 .. N; {自定义子界类型xx（类型名）} Var a: array[xx] of boolean; i,j: integer; Begin Fillchar(a,sizeof(a),true); a[1] := False; for i:=2 to Trunc(sqrt(N)) do if a[I] then for j := 2 to N div I do a[I*j]:= False; t:=0; for i:=2 to N do if a[i] then Begin write(a[ i ]:5); inc(t); if t mod 5=0 then writeln end; End. 【例3】输入十个正整数，把这十个数按由大到小的顺序排列（将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序中的“简单选择排序”是一种较简单的方法） 分析：要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……；因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。 例如下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如 孪生素数猜想初等证明详解 齐宸 孪生素数是指相差2的素数对，例如3和5，5和7，11和13…。孪生素数猜想正式由希尔伯特在1900年国际数学家大会的报告上第8个问题中提出，可以这样描述：存在无穷多个素数p，使得p + 2是素数。 素数对（p, p + 2）称为孪生素数。 孪生素数由两个素数组成，相差为2。为了证明孪生素数猜想，无数的数学家曾为之奋斗，但美丽的公主仍然犹抱琵琶半遮面。 1．孪生素数分类及无个位表示方法 孪生素数按两个素数个位不同划分3类（不包括10以下的3-5、5-7），分别是： 1、孪生素数中两个素数个位为1和3，如11-13，41-43等； 2、孪生素数中两个素数个位为7和9，如17-19，107-109等； 3、孪生素数中两个素数个位为9和1，如29-31，59-61等。 三类孪生素数中个位为1和3的第一类是我们需要重点研究的，其他两类可以忽略不计。因为只要第一类孪生素数无限，也就等价于证明了孪生素数猜想。 自有孪生素数概念以来它们就是由两个素数表示的。若是能简化成一个数字那孪生素数猜想这一世界数学难题也许就向前迈进了一步。无论这一步是一小步，还是一大步。但毕竟能将两个素数组成的孪生素数降格成了像素数那样的单个数字。 分析一下个位为1和3的这一类孪生素数，如41-43这对孪生素数。首先，分别去掉个位1和3后，可以看到剩下了两个数字4和4。用这两个数字完全可以表示一对孪生素数，当然我们心里要想着在这两个数字后面是有个位1和3的。其次，这两个去掉个位的数字又是完全相同的，都是一个数字“4”。这样也就完全可以用一个数字“4”来表示一对孪生素数，也可以说4是一个单数字无个位孪生素数。当然表面上看只有第一类、第二类孪生素数可以用一个数字表示（实际上第三类也可以）。 为什么一定要去掉个位呢？ 可将自然数变成互为补集的两类：孪生素数和非孪生素数。并利用一种简单的筛法，将自然数中的非孪生素数及其补集孪生素数分开。而且这个筛法所要得到的是非孪生素数。并用非孪生素数证明孪生素数猜想。 自然数分成互补的孪生素数与非孪生素数，这是一种新的观点。恐怕没有人相信这种新奇的想法，但这是可以实现的。而且还可以将自然数分成互补的四胞胎素数与非四胞胎素数等。 求孪生素数问题 问题求孪生素数问题。孪生素数是指两个相差为2的素数，例如：3和5，5和7，11和13 等。编程实现输出15对孪生素数。 分析判断是否是循环需要循环，找到15对孪生素数也需要循环，因此该问题是二重循环问题。 数据要求 问题中的常量： 无 问题的输入： 无。 问题的输出： 15对孪生素数。 设计初始算法 1 初始化nCount为零。 2 从2开始判断某个数是否是素数，并且这个数加2是不是素数 3 找到15对孪生素数，结束。 算法细化 我们在循环中引入一个nCount来控制找到15对孪生素数就行。 附加的程序变量 Int nCount=0； 步骤2的细化 2.1 判断某个数是否是素数 2.2 判断这个数加2是不是素数 其中步骤2可以进一步细化，因为求素数是一个简单的问题，我们需要判断比这个 数小的数中，除了它本身和1之外，还有没有别的约数就可以了。 步骤2.1细化 2.1 for(i=2;i<=n-1;i++) 如果(n%i==0) { break; } 流程图 实现 #include "stdio.h" #include "math.h" int isprime(int n) { int nRet=1; int i; if(n<2) nRet=0; for(i=2;i<=n-1;i++) if(n%i==0) { nRet=0; break; } return nRet; } main( ) { int k=2，nCount=0； do { if（isprime（k）&&isprime（k+2）） { nCount+=1； printf（“%d，%d”，k，k+2）； } k=k+1； } while（n<15）； } 测试输出15对孪生素数，略。 孪生素数 要介绍孪生素数，首先当然要说一说素数这个概念。 素数是除了1 和它本身之外没有其它因子的自然数。素数是数论中最纯粹、最令人着迷的概念。除了 2 之外，所有素数都是奇数(因为否则的话除了 1 和它本身之外还有一个因子2，从而不满足素数的定义)，因此很明显大于2 的两个相邻素数之间的最小可能间隔是2。 所谓孪生素数指的就是这种间隔为2 的相邻素数，它们之间的距离已经近得不能再近了，就象孪生兄弟一样。最小的孪生素数是(3, 5)，在100 以内的孪生素数还有(5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) 和(71, 73)，总计有8 组。但是随着数字的增大，孪生素数的分布变得越来越稀疏，寻找孪生素数也变得越来越困难。那么会不会在超过某个界限之后就再也不存在孪生素数了呢？ 我们知道，素数本身的分布也是随着数字的增大而越来越稀疏，不过幸运的是早在古希腊时代，Euclid 就证明了素数有无穷多个 (否则今天许多数论学家就得另谋生路)。长期以来人们猜测孪生素数也有无穷多组，这就是与Goldbach 猜想齐名、集令人惊异的简单表述和令人惊异的复杂证明于一身的著名猜想- 孪生素数猜想： 孪生素数猜想：存在无穷多个素数p, 使得p+2 也是素数。 究竟谁最早明确提出这一猜想我没有考证过，但是一八四九年法国数学Alphonse de Polignac 提出猜想：对于任何偶数2k, 存在无穷多组以2k 为间隔的素数。对于k=1，这就是孪生素数猜想，因此人们有时把Alphonse de Polignac 作为孪生素数猜想的提出者。不同的k 对应的素数对的命名也很有趣， 1．自然数是0，1，2…… 2．素数是2，3，5……（不包括1的只能背1和它本身整除的自然数） 【1】求10000以内的所有素数。 素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。像著名的哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研，呕心沥血，但至今仍然未见分晓。 自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数。 求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。 但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。 第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不 必再用其他的数去除。 第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际 上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。 第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明： 如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。 如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。 而这是不可能的，所以，d1和d2中必有一个小于或等于√N。 基于上述分析，设计算法如下： (1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。 (2)用100以内的所有素数逐个试除的方法求出10000以内的素数。 首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A 数组中的一个单元中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。 【2】用筛法求素数。 简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的 何为线性筛法，顾名思义，就是在线性时间内（也就是O（n））用筛选的方法把素数找出来的一种算法，没用过线性筛素数法的人可能会奇怪，用遍历取余判定素数不是也是线性时间的吗，没错，但是确切的说线性筛法并不是判定素数的，而是在线性时间内求出一个素数表，需要判定是否是素数的时候只要看该数是否在表内就可以瞬间知道是不是素数。 比如想求10000以内的素数，定义表int a[10000]，进行线性筛选后，a[n]的值就代表n是不是素数，a[n]如果是1，就代表n是素数，a[n]如果是0，就代表n不是素数，这就是查表。再判定其他的素数也是一样，不用再做任何计算。 而如果用遍历取余，那么每判定一个数都要从头开始再遍历一遍，而线性筛法只在开始一次性运算完，以后只要查表即可，查表通常只需要1条语句。所以如果你的程序从始至终只需要判定那么几次素数那么用遍历取余即可，但是如果需要多次判定素数，而且这个数还不是很小的话，那么线性筛法就会体现出巨大的优越性来。 线性筛法的核心原理就是一句话：每个合数必有一个最大因子（不包括它本身），用这个因子把合数筛掉，还有另一种说法（每个合数必有一个最小素因子，用这个因子筛掉合数，其实都一样，但是我觉得这种方法不太容易说明，这种方法我会在最后给出简略说明）。这个很容易证明：这个小学就知道合数一定有因子，既然是几个数，就一定有最大的一个。最大因子是唯一的，所以合数只会被它自己唯一的因子筛掉一次，把所有合数筛掉后剩下的就全是素数了。 先假设一个数i，一个合数t，i是t最大的因数，t显然可能并不唯一（例如30和45的最大因数都是15）。那么如何通过i知道t呢，t必然等于i乘以一个比i小的素数。先来说这个数为什么一定要比i小，这很显然，如果是i乘上一个比它大的素数，那么i显然不能是t 最大的因子。再来说为什么要是素数，因为如果乘上一个合数，我们知道合数一定可以被分解成几个素数相乘的结果，如果乘上的这个合数x=p1*p2*……，那么 t = i * x = i * p1 * p2……很显然p1* i也是一个因数，而且大于i。所以必须乘上一个素数。 比i小的素数一定有不少，那么该乘哪一个呢，既然t不唯一，那么是不是都乘一遍呢？很显然不行，虽然t不唯一，但全乘一遍很显然筛掉的数的数量远远超过合数的数量。我们先给出结论： 任意一个数i = p1*p2*……*pn，p1、p2、……pn都是素数，p1是其中最小的素数， 设T 为i * M的积（显然T就成了一个合数），也就是T = i * M，（M是素数，并且M<=p1）,那么T的最大的因数就是i。 是的，乘上的数要小于等于i最小的质因数。 PS：本来没有决心把这个东西写完的，结果早上写到一半，出去吃个饭，没保存，回来手一抖直接关掉了，好不容易写了一大半了，只能重新写了，坑爹啊，但就是这个插曲，本来还没有决心的我，一下子却坚定了信念，一点要把这个东西写完。就这样开始吧 BY：Lee 下面，我们重新开始 ═══════════════════════════════════════════ 如何判断一个数是否是素数呢 ═══════════════════════════════════════════也许你会认为这是一个简单的问题，但事实上，世界上任何一个问题，都没有你想象中的那么简单1 + 1 是否等于2 ，这便是一个简单而又复杂的问题，呵呵。 突然想把这个东西换一种风格来写了，就这样扯淡扯下去吧。扯的时候文章中多少有内容来自于网络，没有侵权的意思，如果作者看到还请见谅。 ═══════════════════════════════════════════下面正式进入正题 ═══════════════════════════════════════════ 一、朴素判断素数 ═══════════════════════════════════════════1. 这种方法被誉为笨蛋的做法： 一个数去除以比它的一半还要大的数，一定除不尽的，这还用判断吗？？ 很容易发现的，这种方法判断素数，对于一个整数n，需要n-2 次判断，时间复杂度是O(n)在n非常大或者测试量很大的时候，这种笨蛋做法肯定是不可取的。 2. 改进一下下小学生的做法： 3. 再改进一下聪明的小学生的做法 对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同一个明显的优化，就是只要从2枚举到√n 即可。 因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。 在这里，这个聪明的小学生还用了i*i <= n 来代替sqrt（n）， 这里是避免了调用函数sqrt（），其消耗时间很大， 特别是在大量数据测试的时候消耗很明显。 这个算法的时间复杂度，与最前面的笨蛋做法就好多了， 不过这里好像用sqrt()也没问题啊，，，，这个就不太清楚了。 但是做一个测试发现，如果是这样额话，每一次判断都要计算i*i， 素数的线性筛法 //整体思想是从自然数 2 开始与所有之前已经确定的素数相乘后的数标记为合数就能把素数一个不漏地找出来 #include 孪生素数筛法 齐宸 首先研究一下个位为3的合数。 要想两数相乘的结果个位为3，这两数字的个位有且只有两种组合1、3或7、9。自然数(10k+1)乘以自然数(10i+3)，可以利用初中数学将其转化为10[(10i+3)k+i]+3形式。去个位后转换为(10i+3)k+i。 同法可得个位为1、3、7、9全部无个位合数公式，结果如下: 个位为1：(10i+1)k+i、(10i+3)k+7i+2、(10i+9)k+9i+8 个位为3：(10i+3)k+i、(10i+7)k+9i+6 个位为7：(10i+7)k+i、(10i+3)k+9i+2 个位为9：(10i+9)k+i、(10i+3)k+3i、(10i+7)k+7i+4 这里的关键是去掉个位。 显然个位为1的无个位合数公式可以求得所有个位为1的合数，计算结果中没有的数字必是个位为1的素数，也就说可以筛出所有个位为1的素数。这实际上就是个位为1的素数筛法。 同样个位1和个位为3的5组无个位合数公式合用，可以计算得到所有个位为1和个位为3的合数，也就等同于得到了任意一个自然数内所有个位为1和3的非孪生素数。而剩余数字全部是孪生素数。此时的非孪生素数与孪生素数不是2个数字，全部是一个数字。比如个位1和个位为3的5组无个位合数公式合用能计算出10以下9个数字中的6个数字，分别是2、3、5、6、8、9，这些无个位数字分别填上个位数字1、3后变成两个数字，如2变成21-23显然这组不是孪生素数。同样，31-33、51-53、61-63、81-83、91-93也不是孪生素数。而计算结果中没有的数字1、4、7，这3个数字填上个位1和3后分别变成了11-13、41-43、71-73，全部是孪生素数。这种方法实质上就是孪生素数筛法。当然仅是个位为1和3的这类孪生素数。（17-19和29-31这样类型的孪生素数变换公式后也可求出）。 这里有三个新观点： 1、孪生素数可以用一个数字指代。 如用1指代孪生素数11-13，用4指代孪生素数41-43。相反的如2、3是非孪生素，分别对应的是21-23和31-33。 2、孪生素数存在补集：非孪生素数。 筛法 筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。 具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。） 例如，用筛法找出不超过30的一切质数： 不超过30的质数2，3，5，7，11，13，17，19，23，29共10个。 使用pascal语言，利用筛法求素数的代码： ReadLn(n);｛需要求2~n之间所有的素数｝ For i:=2 To n Do a := True;｛全部清成真，表示目前是素数｝ For i:=2 To n Do If a Then｛当该数纪录是质数时开始筛选｝ For j:=1 To n Div i Do a[2 * j] := False;｛筛掉所有质数的倍数｝ sum := 0;｛统计范围内有多少个质数｝ For i:=2 To n Do If a Then Begin｛如果是质数就输出｝ Write(i, ' '); Inc(sum); End; WriteLn（sum）;｛输出总数｝ readln(n);(读入N); for i:=2 to n do a[i]:=true;(先将a数组全部定义为素数,即用true代表素数,false 合数) for i:=2 to trunc(sqrt(n)) do(1 to n 也可以,不过比较浪费时间) begin if a[i]=true then (如果这个数是素数,则执行.这样比较省时间) begin for j:=2 to n div i do a[i*j]=false;(将一切可以被2、3、4...整除的数全部定义为合数) end; ★引子 前天，俺在《俺的招聘经验[4]：通过笔试答题能看出啥？》一文，以"求质数"作为例子，介绍了一些考察应聘者的经验。由于本文没有政治敏感内容，顺便就转贴到俺在CSDN 的镜像博客。 昨天，某个CSDN网友在留言中写道： 老实说,这个程序并不好写,除非你背过这段代码 如果只在纸上让别人写程序,很多人都会出错 但是如果给一台电脑,大多数人都会把这个程序调试正确 出这个题目没啥意义 只能让别人觉得你出题水平低 首先，这位网友看帖可能不太仔细。俺在文中已经专门强调过了，评判笔试答题，"思路和想法"远远比"对错"更重要，而他/她依然纠结于对错；其次，这位网友居然觉得这道题目没啥意义，这让俺情何以堪啊？！看来，有相当一部分网友完全没有领略到此中之奥妙啊！ 算了，俺今天就豁出去了，给大伙儿抖一抖这道题目的包袱。当然，抖包袱的后果就是：从今天开始，就得把"求质数"这道题从俺公司的笔试题中去掉，然后换上另外一道全然不同的。这么好的一道题要拿掉，真是于心不忍啊 :-( ★题目 好，言归正传。下面俺就由浅入深，从各种角度来剖析这道题目的奥妙。 为了避免被人指责为"玩文字游戏"（有些同学自己审题不细，却抱怨出题的人玩文字游戏），在介绍各种境界之前，再明确一下题意。 前一个帖子已经介绍过，求质数可以有如下2种玩法。 ◇需求1 请实现一个函数，对于给定的整型参数 N，该函数能够把自然数中，小于 N 的质数，从小到大打印出来。 比如，当 N = 10，则打印出 2 3 5 7 ◇需求2 请实现一个函数，对于给定的整型参数 N，该函数能够从小到大，依次打印出自然数中最小的 N 个质数。 比如，当 N = 10，则打印出 2 3 5 7 11 13 17 19 23 29 ★试除法 首先要介绍的，当然非"试除法"莫属啦。考虑到有些读者是菜鸟，稍微解释一下。 "试除"，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。 显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过捏，这个最平庸的思路，居然也有好多种境界。大伙儿请看： ◇境界1 在试除法中，最最土的做法，就是： 假设要判断 x 是否为质数，就从 2 一直尝试到 x-1。这种做法，其效率应该是最差的。如果这道题目有10分，按照这种方式做出的代码，即便正确无误，俺也只给1分。 ◇境界2 稍微聪明一点点的程序猿，会想：x 如果有（除了自身以外的）质因数，那肯定会小于等于 x/2，所以捏，他们就从 2 一直尝试到 x/2 即可。 这一下子就少了一半的工作量哦，但依然是很笨的办法。打分的话，即便代码正确也只有2分 ◇境界3 再稍微聪明一点的程序猿，会想了：除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数。 这一下子，工作量又少了一半哦。但是，俺不得不说，依然很土。就算代码完全正确也只能得3分。 ◇境界4 比前3种程序猿更聪明的，就会发现：其实只要从 2 一直尝试到√x，就可以了。估计有些网友想不通了，为什么只要到√x 即可？ 简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。至于严密的数学证明，用小学数学知识就可以搞定，俺就不啰嗦了。◇境界5 那么，如果先尝试2，然后再针对 3 到√x 的所有奇数进行试除，是不是就足够优了我发现了筛法的计算公式(最后稿)
C语言求质数
素数普遍公式
孪生素数个数公式
筛法求素数
用筛法求出100以内的全部素数
孪生素数猜想初等证明详解
求孪生素数问题
孪生素数
C语言求素数问题算法
线性筛法求素数的原理与实现
素数的几种判断方法和实现
素数的线性筛法
孪生素数筛法
筛法求素数
质数分解