int64内Miller-Rabin素数测试和Pollard_Rho_因数分解算法实现

Int64以内Rabin-Miller 强伪素数测试 和Pollard ρ因数分解的算法实现

在求解POJ1811题Prime Test 中应用到的两个重要算法是Rabin-Miller 强伪素数测试和Pollard ρ因数分解算法。前者可以在()n O log 的时间内以很高的成功概率判断一个整数是否是素数。后者可以在最优()

4n O 的时间内完成合数的因数分解。这两种算法相对于试除法都显得比较复杂。本文试图对这两者进行简单的阐述，说明它们在32位计算机上限制在64位以内的条件下的实现中的细节。下文提到的所有字母均表示整数。

一、Rabin-Miller 强伪素数测试

Rabin-Miller 强伪素数测试的基本思想来源于如下的Fermat 小定理： 如果p 是一个素数，则对任意a 有()p a a p mod ≡。特别的，如果p 不能整除a ，则还有()p a p mod 11≡-。

利用Fermat 小定理可以得到一个测试合数的有力算法：对1>n ，选择1>a ，计算()n a n mod 1-，若结果不等于1则n 是合数。若结果等于1则n 可能是素数，并被称为一个以a 为基的弱可能素数（weak probable prime base a ，a -PRP ）;若n 是合数，则又被称为一个以a 为基的伪素数（pseudoprime ）。

这个算法的成功率是相当高的。在小于25,000,000,000的1,091,987,405个素数中，一共只用21,853个以2为基的伪素数。但不幸的是，Alford 、Granville 和Pomerance 在1994年证明了存在无穷多个被称为Carmichael 数的整数对于任意与其互素的整数a 算法的计算结果都是1。最小的五个Carmichael 数是561、1,105、1,729、2,465和2,801。

考虑素数的这样一个性质：若n 是素数，则1对模n 的平方根只可能是1和1-。因此1

-n a

对模n 的平方根2

1

-n a

也只可能是1和1-。如果

2

1

-n 本身还是一个偶数，我们可以再取一次平方根……将这些写成一个算法：

（Rabin-Miller 强伪素数测试）记d n s 21=-，其中d 是奇数而s 非负。如果

()n a d mod 1≡，或者对某个s r <≤0有()n a d r

mod 12-≡，则认为n 通过测试，并

称之为一个以a 为基的强可能素数（strong probable prime base a ，a -SPRP ）。若n 是合数，则又称之为一个以a 为基的强伪素数（strong pseudoprime ）。

这个测试同时被冠以Miller 的名字是因为Miller 提出并证明了如下测试：如果扩展黎曼猜想（extended Riemann hypothesis ）成立，那么对于所有满足

()2

log 21n a <<的基a ，n 都是a -SPRP ，则n 是素数。

尽管Monier 和Rabin 在1980年证明了这个测试的错误概率（即合数通过测试的概率）不超过

4

1

，单个测试相对来说还是相当弱的（Pomerance 、Selfridge 和Wagstaff, Jr.证明了对任意1>a 都存在无穷多个a -SPRP ）。但由于不存在“强Carmichael 数”（任何合数n 都存在一个基a 试之不是a -SPRP ），我们可以组合多个测试来产生有力的测试，以至于对足够小的n 可以用来证明其是否素数。

取前k 个素数为基，并用k ψ来表示以前k 个素数为基的强伪素数，Riesel 在1994年给出下表：

321

,972,326,370,024,942,526,193,897,56401,002,541,205,143,073,566,360,553,1041,689,705,135,316,234,41321

,728,071,550,341321,728,071,550,341383,660,749,474,3747,898,302,152,2751,031,215,3001,326,25653,373,1047

,21110987654321≤≤≤========ψψψψψψψψψψψ 考虑到64位二进制数能表示的范围，只需取前9个素数为基，则对小于8

ψ的所有大于1的整数测试都是正确的；对大于或等于8ψ并小于642的整数测试错误的概率不超过

18

21。 Rabin-Miller 强伪素数测试本身的形式稍有一些复杂，在实现时可以下面的

简单形式代替：

对1>n ，如果()n a n mod 11≡-则认为n 通过测试。 代替的理由可简单证明如下：

仍然记d n s 21=-，其中d 是奇数而s 非负。若n 是素数，由()n a n mod 11≡-可以推出()n a a n s d

mod 121

1

2

-≡≡--或()n a d

s mod 11

2

≡-。

若为前者，显然取1-=s r 即可使n 通过测试。若为后者，则继续取平方根，直到对某个s r <≤1有

()n a d r

mod 12-≡，或()n a d mod 12≡。无论()n a d mod 1≡还是()n a d mod 1-≡，n

都通过测试。

Rabin-Miller 强伪素数测试的核心是幂取模（即计算()n a s mod ）。计算幂取模有以下的()n O log 算法（以Sprache 伪代码语言描述）：

这个算法在32位计算机上实现的难点在于指令集和绝大部分编程语言的编译器都只提供了32位相乘结果为64位的整数乘法，浮点运算由于精度的问题不能应用于这里的乘法。唯一解决办法是模仿一些编译器内建的64位整数乘法来实现两个无符号64位相乘结果为128位的乘法。这个乘法可以将两个乘数分别分割成两个32位数来实现。为方便乘法之后的取模运算，运算结果应当用连续的128个二进制位来表示。以下是其伪代码：

乘法之后的取模运算可以用浮点运算快速完成。具体做法是乘积的高64位和低64位分别先对除数取模，然后再利用浮点单元合并取模。这里的浮点运算要求浮点单元以最高精度运算，计算前应先将浮点单元控制字中的精度控制位设置为64位精度。为保证精度，应当用80位浮点数实现此运算。伪代码如下：

至此，Rabin-Miller 强伪素数测试的核心已经全部实现。

二、Pollard ρ因数分解算法

Pollard ρ因数分解算法又称为Pollard Monte Carlo 因数分解算法。它的核心思想是：选取一个随机数a 。再选一个随机数b 。检查()n b a ,gcd -是否大于1。

若大于1，()n b a ,gcd -就是n 的一个因子。若不大于1，再选取随机数c ，检查

()n b c ,gcd -和()n a c ,gcd -。如此继续，直到找到n 的一个非平凡因子。

它的主要实现方法是从某个初值n x <<10出发，通过一个适当的多项式()x f 进行迭代，

产生一个伪随机迭代序列{}()()(){} ,,,,,,111321x f f x f x x x x =直到其对模n 出现循环。多项式()x f 的选择直接影响着迭代序列的长度。经典的选择是选取()a x x f +=2，其中()n a mod 2,0-≠。不选择0和2-的原因是避免当序列中某一项()n x k mod 1±≡时后续各项全部为1的情况。迭代序列出现循环的期望时间和期望长度都与n 成正比。设n 有一个非平凡因子p 。由前面可知，迭代序列关于模p 出现循环的期望时间和期望长度与p 成正比。当循环出现时，设()p x x k j mod ≡，记()n x x d k j ,g cd -=，则d 是p 的倍数。当n d ≠时，d 就是n 的一个非平凡因子。

但是在分解成功之前，p 是未知的，也就无从直接判断循环是否已经出现。仍然设迭代序列关于模p 出现循环，()p x x k j mod ≡并设k j <。由取模运算的性质可知()()()n x f x f k j m o d ≡，即()p x x k j m o d

11++≡。故对任意0≥c ，总有()p x x c k c j m o d ++≡。记循环部分长度为t ，若k t ，则k t 2，那么()n x x k k mod 2≡。因此，只要对迭代序列中的偶数项k x 和对应的k x 计算()

n x x d k k ,gcd -=。只要

n d ≠，d 就是n 的一个非平凡因子。以上就是Pollard 原来建议使用的Floyd 循

环判断算法。由此得到Pollard ρ因数分解算法的第一个伪代码：

Floyd 循环判断算法对储存整个迭代序列的空间要求很高，一般实现时都使用时间换空间的办法，同时计算k x 和k x 2来进行判断（如上面的伪代码）。Brent 提出了另外一种效率更高的循环判断算法：每步只计算k x ，当k 是2的方幂时，令k x y =；每一步都拿当前的k x 和y 计算()n y x d k ,gcd -=。伪代码如下：

由于循环出现的时空期望都是()p O

，Pollard ρ因数分解算法的总体时间复

杂度也就是()p O 。在最坏情况下，其时间复杂度可能接近()n O ，但在一般条件下，时间复杂度都可以认为是()4

n O 。

参考资料：

Chris Caldwell “Fermat, probable-primality and pseudoprimes.”Chris Caldwell “Strong probable-primality and a practical test.”Eric W. Weisstein “Brent’s Factorization Method.”

Eric W. Weisstein “Pollard Rho Factorization Method.”

Eric W. Weisstein “Rabin-Miller Strong Pseudoprime Test.”Eric W. Weisstein “Strong Pseudoprime.”

Unknown Author “Pollard’s ρ.”

孪生素数猜想初等证明详解

孪生素数猜想初等证明详解 齐宸 孪生素数是指相差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是一个单数字无个位孪生素数。当然表面上看只有第一类、第二类孪生素数可以用一个数字表示（实际上第三类也可以）。 为什么一定要去掉个位呢？ 可将自然数变成互为补集的两类：孪生素数和非孪生素数。并利用一种简单的筛法，将自然数中的非孪生素数及其补集孪生素数分开。而且这个筛法所要得到的是非孪生素数。并用非孪生素数证明孪生素数猜想。 自然数分成互补的孪生素数与非孪生素数，这是一种新的观点。恐怕没有人相信这种新奇的想法，但这是可以实现的。而且还可以将自然数分成互补的四胞胎素数与非四胞胎素数等。

PAT计算机能力考试乙级1-10题答案

1001 害死人不偿命的(3n+1) 猜想（15 分 对任何一个正整数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在1950年的世界数学家大会 上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3 n+1) ，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展?? 我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？ 分析：输入一个正整数 n 进行循环， n=1 循环截止 , 判断 n, 如果它是偶数，那么把它砍掉一半； 如果它是奇数，那么把 (3 n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1， 并计算经过的次数m。 #include"stdlib.h" #include"stdio.h" int main() { int n,m; m=0; scanf_s("%d",&n); while(n!=1) { if(n%2==0) { n=n/2; } else { n=(3*n+1)/2; } m++; } printf_s("%d\n",m); system("pause"); } 1002 写出这个数（20分） 读入一个正整数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。 分析：输入一个正整数n， while循环求出n的各位数字之和sum；如果 sum 等于 0，那么就输出它的拼音”ling ”；如果不等于0，输入数组 b 存放各位数字之和，在switch对这个数组进行判断数组 b 各个数的数值为多少，0 对应 "ling"; 1 对应 "yi";2:对应<"er";3对应"san";4对应"si";5对应"wu";6对应"liu";7对应"qi";8对应 "ba";9对应"jiu";

奇异的素数规律现象(一)

奇异的素数规律现象（一） 江苏省南通市崇川区张忠(言) 在对素数规律的探索中, 我发现了一些令人难以置信的奇异现象如下: 现象一现利用某一确定的规则给出模2x3x5x7的两个最小非负剩余集: B={1,29,41,47,163,169,181,209.}, Y={0,12,18,30,42,60,72,102,108,138,150,168,180,198.} 则可发现以下两种情况: 情况甲: 1) 当b-y>0时: b-y与b+y是和为偶数2b的一对模210的简化剩余(类); 2) 当b-y>1,b+y<121时: b-y与b+y是和为偶数2b的一对奇素数. 例:59-0与59+0; 59-12与59+12;...59-48与59+48 都是和为偶数2b=118的一对奇素数. 等等,等等. 情况乙: 1)当y-1>0时: y-1与y+1为模210的孪生简化剩余(类). 2)当y-1>0且y+1<121时: y-1与y+1为孪生素数.例: 12-1与12+1; 18-1与18+1; 30-1与30+1; 42-1与42+1; 60-1与60+1 72-1与72+1 102-1与102+1 108-1与108+1 都是孪生素数. 现象二现仍用上面确定的同一规则给出模2x3x5x7的两个最小非负剩余集: B={2,58,68,82,128,142152,208.}, Y={15,21,39,45,69,81,99,105.} 则可发现以下情况: 情况甲: 1) 当b-y>0时: b-y与b+y是和为偶数2b的一对模210的简化剩余(类); 2) 当b-y>1,b+y<121时: b-y与b+y是和为偶数2b的一对奇素数. 情况乙 1) 当y-1>0时: y-2与y+2为模210的相差为4的一对简化剩余(类). 2)当y-2>0且y+2<121时: y-2与y+2为一对相差为4的素数.例: 15-2与15+2; 21-2与21+2; 39-2与39+2; ...105-2与105+2. 都是相差为4的素数对. 敬请各位老师指教! ... ... (未完待续!)

PAT计算机能力考试乙级110题答案

1001害死人不偿命的(3n+1)猜想(15 分 对任何一个正整数n,如果它就是偶数,那么把它砍掉一半;如果它就是奇数,那么 把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,拼命想证明这个貌似很傻很天真的命题,结果闹得学生们无心学业,一心只证(3n+1),以至于有人说这就是一个 阴谋,卡拉兹就是在蓄意延缓美国数学界教学与科研的进展…… 我们今天的题目不就是证明卡拉兹猜想,而就是对给定的任一不超过 1000 的正整数n,简 单地数一下,需要多少步(砍几下)才能得到n=1？ 分析:输入一个正整数n进行循环,n=1循环截止,判断n,如果它就是偶数,那么把它砍掉一半;如果它就是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得 到n=1,并计算经过的次数m。 #include"stdlib、h" #include"stdio、h" int main() { int n,m; m=0; scanf_s("%d",&n); while(n!=1) { if(n%2==0) { n=n/2; } else { n=(3*n+1)/2; } m++; } printf_s("%d\n",m); system("pause"); } 1002写出这个数(20 分) 读入一个正整数n,计算其各位数字之与,用汉语拼音写出与的每一位数字。 分析:输入一个正整数n, while循环求出n的各位数字之与sum;如果sum等于0,那么就输出它的拼音”ling”;如果不等于0,输入数组b存放各位数字之与,在switch对这个数组进行判断数组b各个数的数值为多少,0对应"ling"; 1对应"yi";2:对应<"er";3对应"san";4对应"si";5对应"wu";6对应"liu";7对应"qi";8对应"ba";9对应"jiu";

深圳市必修第二册第五单元《概率》测试卷(包含答案解析)

一、选择题 1．孪生素数猜想是希尔伯特在1900年提出的23个问题之一，2013华人数学家张益唐证明了孪生素数猜想是一个弱化形式，问题可以描述为：存在无穷多个素数p ，使得2p +是素数，素数对(,2)p p +称为孪生素数对，问：如果从30以内的素数组成的孪生素数对中随机抽取一对，这对孪生素数的积超过20的概率为（ ）． A ． 23 B ． 34 C ． 45 D ． 56 2．某城市2017年的空气质量状况如下表所示： 其中污染指数50T ≤时，空气质量为优；50100T <≤时，空气质量为良； 100150T <≤时，空气质量为轻微污染，该城市2017年空气质量达到良或优的概率为（ ） A ．35 B ．1180 C ．119 D ．56 3．某次战役中，狙击手A 受命射击敌机，若要击落敌机，需命中机首2次或命中机中3次或命中机尾1次，已知A 每次射击，命中机首、机中、机尾的概率分别为0.2、0.4、0.1，未命中敌机的概率为0.3，且各次射击相互独立．若A 至多射击两次，则他能击落敌机的概率为（ ） A ．0.23 B ．0.2 C ．0.16 D ．0.1 4．一道竞赛题，A ，B ，C 三人可解出的概率依次为1 2，13，14 ，若三人独立解答，则仅有1人解出的概率为（ ） A ． 1 24 B ． 1124 C ．1724 D ．1 5．随机抛掷一枚质地均匀的骰子，记正面向上的点数为a ，则函数()2 24 f x x ax =++至多有一个零点的概率为（ ） A ． 13 B ． 12 C ． 23 D ． 56 6．设两个独立事件A 和B 同时不发生的概率是p ,A 发生B 不发生与A 不发生B 发生的概率相同,则事件A 发生的概率为( )

关于质数问题的讨论

第1章前言 质数在研究整数的过程中占有一个很重要的地位，它被称为自然数的“建筑的基石”．虽然有很多数学家和学者致力于对它的研究，但成果并不显著，仍有许多问题有待解决．例如，哥德巴赫猜想困扰了人们几百年，有很多数学家对它进行了多年的研究但并没有得到解决．我国数学家陈景润的“陈氏理论”是迄今为止世界上关于哥德巴赫猜想研究的最好成果．这一成果给后人很大鼓舞，似乎离最后结果仅一步之遥，但仍一直无进展．梅森质数是数论研究的一项重要内容，研究梅森质数具有重大的意义，也是当今科学探索的热点和难点之一．随着现代科学技术的迅速发展，也加快了对质数的研究．运用计算机能够较快的计算某自然数是否是质数，知道在某范围内质数的分布情况．由于质数的无穷性，要想计算更大的质数仅有计算机还远远不够，还需要有更高的理论要求．同时，质数在加密和解密技术中的应用有了更高的要求，求尽可能大的质数和大数分解引起了通讯界和数学界的极大兴趣．另外，质数在奥数中也屡屡出现，技巧性非常强，可以锻炼和提高学生的思维．所以有必要对质数的相关问题进行阐述． 本文着重介绍质数相关问题，能够使读者形象、直观地目睹质数分布规律，了解有关质数问题． 首先，在质数基本知识中介绍质数的定义、性质及算术基本定理，并讨论判定质数的两个定理一个是威尔逊定理和另一个判定定理； 其次，研究质数个数问题，质数分布问题，得到质数个数有无穷多个，在某两个自然数之间大约有多少质数和两个相邻质数的间隙可以任意大等结论．还介绍用幼拉脱斯展纳筛法和质数辐射法来求从1到某自然数n之间所有的质数，进而分析质数的分布问题，并讨论它们的区别； 最后，介绍有关质数的著名问题，如费马质数是否有有限，梅森质数是否有无穷多个，什么是孪生质数，并用聚数来研究孪生质数对一些性质，哥德巴赫猜想的由来、研究意义等问题，以及它们理论的推广与应用．

压力式喷雾干燥塔各主要工艺控制参素数对产品质量的影响

压力式喷雾干燥塔各主要工艺 控制参素数对产品质量的影响 廖庆禄 （福建杨振华851生物科技股份有限公司，福建福州350015）摘要：通过对GNT～101型压力式喷雾干燥塔使用时各控制参素数的分析，指出喷雾过程各主要控制参素数对产品质量有着不同的影响，并探讨了他们之间的相互关系，明确了当某个参数发生变化，其它参数也应做相应调整，以及对于不同品种控制参数是不同的，应根据实验总结出不同的控制参数要求。 喷雾干燥是液体工艺成形和干燥工业中最广泛应用的工艺。最适用于从溶液、乳液、悬乳液和可泵性糊状液体原料中生成粉状、颗粒状或块状固体产品。在制药工业中，喷雾干燥常用于对中药提取浓缩液的干燥，药品生产中，通常对药粉的颗粒大小分布、残留水份含量、堆积密度和颗粒形状色泽有着不同的要求。要想达到要求就需对喷雾干燥过程各控制参数对产品质量的影响加以分析。目前所使用的喷雾干燥器主要有压力式、气流式、和离心式三种。压力式喷雾干燥器（又称喷雾干燥塔）在生产中使用最普遍。压力式喷雾干燥器的产品成微粒状，一般平均粒度可达150-200um左右，产品有良好的流动性、润湿性、润滑性等应用性能，所以深受用户的欢迎。【1】本文即以作者所在单位使用的上海乳品机械厂生产的GNT～101型压力式喷雾干燥塔为例进行探讨。 1 工作原理 本设备为立式压力喷雾干燥器，物料由高压均质泵经高压管由塔顶均风器中间喷入塔内，经喷头雾化呈70-80度雾化角的雾滴，雾滴与相对湿度很低，经过过滤和加热的再经均风器进入的热风接触，二者瞬间发生强烈的热交换和质交换；热风的热能供给雾滴使其水分蒸发，并干燥成含水分合乎要求的粉粒，蒸发出

来的水分被热风带走，通过袋过滤器由排风机排入大气。其中大部分产品落至塔体圆锥部分，由震锤震落至出粉口连续排至接粉桶（袋）。 2 工作特点 （1）干燥速度快，料液经雾化后表面积大大增加，在热风气流中，瞬间就可蒸发92%-98%的水分，完成干燥时间仅需数秒钟，特别适用于热敏性物料的干燥。该型号设备水分蒸发量为70公斤/小时。 （2）产品具有良好的均匀度、流动性和溶解性，产品纯度高，质量好。 （3）生产过程简化，操作控制方便。对于湿含量40-80%（特殊物料可达90%）的液体能一次干燥成粉粒产品，干燥后不需要粉碎和筛选，减少生产工序，提高产品纯度。对产品粒径、松密度、水份，在一定范围内可通过改变操作条件进行调整，控制和管理都很方便。 （4）适用于热敏性和非热敏性物料的干燥，适用于水溶液和有机溶剂物料的干燥，原料液可以是溶液、泥浆、乳浊液、糊状物或融熔物等均可处理。 （5）喷雾干燥的缺点主要是投资费用比较高和喷雾干燥属于对流型干燥器，热效率比较低（除非利用非常高的温度），一般为30%～40%。【2】 3 生产过程各主要控制工艺参数对产品质量的影响 喷雾干燥过程需要密切注意操作参数的变化，以便生产出符合一定要求的干燥产品。生产过程的每个阶段都能对干燥产品的性能产生一定程度的影响。如雾化方法和料液性质将确定产品的粒度分布、松密度、外观和湿含量。雾滴与空气的接触、干燥室的设计以及实际的干燥操作情况将确定产品的松密度、湿含量、易碎性、口味和活性的保持。在实际生产中，对于特定设备而言，，主要对料液中固含量、料液温度、进风温度、塔内温度、排风温度、塔内真空度、雾化压力和进料速度这几个参数进行控制。3.1 料液中固含量

数学对于计算机的重要性

数学对于计算机的重要性 可能有很多朋友在网上看过google公司早几年的招聘广告，它的第一题如下了:{first 10-digit prime found in consecutive digits e}.com，e中出现的连续的第一个10个数字组成的质数。据说当时这个试题在美国很多地铁的出站口都有大幅广告，只要正确解答了这道题，在浏览器的地址栏中输入这个答案，就可以进入下一轮的测试，整个测试过程如同一个数学迷宫，直到你成为google的一员。 又如Intel某年的一道面试题目:巴拿赫病故于1945年8月31日。他出生年份是他在世某年年龄平方减去这年年龄的差，问:他是哪年出生的?这道看似很简单的数学问题，你能不能很快地解答呢? 下面则是一道世界第一大软件公司微软的招聘测试题:中间只隔一个数字的两个素数被称为素数对，比如5和7，17和19，证明素数对之间的数字总能被6整除(假设这两个素数都大于6)，现在证明没有由三个素数组成的素数对。这样的试题还有很多很多，这些题目乍初看上去都是一些数学问题。但是世界上一些著名的公司都把它们用于招聘测试，可见它们对新员工数学基础的重视。数学试题与应用程序试题是许多大型软件公司面试中指向性最明显的一类试题，这些试题就是考察应聘者的数学能力与计算机能力。 某咨询公司的一名高级顾问曾说:微软是一家电脑软件公司，当然要求其员工有一定的计算机和数学能力，面试中自然就会考察这类能力。微软的面试题目就考察了应聘人员对基础知识的掌握程度、对基础知识的应用能力，甚至暗含了对计算机基本原理的考察。所以，这样的面试题目的确很“毒辣”，足以筛选到合适的人。 四川大学数学学院的曹广福教授曾说过:“一个大学生将来的作为与他的数学修养有很大的关系”。大学计算机专业学生都有感触，计算机专业课程中最难的几门课程莫过于离散数学、编译原理、数据结构，当然像组合数学、密码学、计算机图形学等课程也令许多人学起来相当吃力，很多自认为数据库学得很好的学生在范式、函数依赖、传递依赖等数学性比较强的概念面前感到力不从心，这些都是因为数学基础或者说数学知识的缺乏所造成的。 数学是计算机的基础，这也是为什么考计算机专业研究生数学都采用最难试题(数学一)的原因，当然这也能促使一些新的交叉学科如数学与应用软件、信息与计算科学专业等飞速发展。许多天才程序员本身就是数学尖子，众所周知，BillGates的数学成绩一直都很棒，他甚至曾经期望当一名数学教授，他的母校——湖滨中学的数学系主任弗雷福?赖特曾这样谈起过他的学生:“他能用一种最简单的方法来解决某个代数或计算机问题，他可以用数学的方法来找到一条处理问题的捷径，我教了这么多年的书，没见过像他这样天分的数学奇才。他甚至可以和我工作过多年的那些优秀数学家媲美。当然，比尔也各方面表现得都很优秀，不仅仅是数学，他的知识面非常广泛，数学仅是他众多特长之一”。影响一代中国程序人的金山软件股份有限公司董事长求伯君当年高考数学成绩满分进一步说明了问题。很多数学基础很好的人，一旦熟悉了某种计算机语言，他可以很快地理解一些算法的精髓，使之能够运用自如，并可能写出时间与空间复杂度都有明显改善的算法。 程序设计当中解决的相当一部分问题都会涉及各种各样的科学计算，这需要程序员具有什么样的基础呢?实际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。从中我们不难看出数学在程序设计领域的重要性。算法与计算理论是计算机程序设计领域的灵魂所在，是发挥程序设计者严谨，敏锐思维的有效工具，任何的程序设计语言都试图将之发挥得淋漓尽致。 程序员需要一定的数学修养，不但是编程本身的需要，同时也是培养逻辑思维以及严谨的编程作风的需要。数学可以锻炼我们的思维能力，可以帮助我们解决现实中的问题。可以帮助我们更高的学习哲学。为什么经常有人对一些科学计算程序一筹莫展，他可以读懂

余数原理

余数原理 探索者：王志成 偶数内有众多素数，为什么有的素数能够组成偶数1+1的素数对，有的素数不能组成偶数的素数对，本文原原本本地告诉大家。 令大于6的任意偶数为M，小于√M的素数为素因子，任意素因子为X。二数和等于M 的数对为M/2对，令任意数对为：A+B=M。 令M/X余C，那么，（A+B）/X也必然余C。 A/X余D，B/X余F，那么，D+F=C或X+C。 当，A/X余D，那么，B/X的余数必然为：C-D或（C+X）-D。 当，B/X余F，那么，A/X的余数必然为：C-F或（C+X）-F。 这就是哥德巴赫猜想中，涉及偶数、素数、合数与素因子之间的余数原理。 例一、100/7余2，那么，（11+89）/7也必然余2，因为，11/7余4，所以，89/7的余数必然2-4或（2+7）-4=5。 例二、5432167898=257+5432167641，5432167898/241余183。因为，257/241余16。所以，5432167641/241必然余183-16=167。 该原理的具体应用： 我们取任意偶数，986，√986≈31，该偶数有素因子2，3，5，7，11，13，17，19，23，29，31， 偶数除以素因子的余数为：986/2余0，986/3余2，986/5余1，986/7余6，986/11余7，986/13余11，986/17余0，986/19余17，986/23余20，986/29余0，986/31余25。 1、根据这些余数，我们可以求得该偶数： （1）、除以2余0的数列为：2+2N， （2）、把2+2N数列取3项为：2，4，6。除以3余2的只有2。数列为2+6N， （3）、把2+6N数列取5项为：2，8，14，20，26，除以5余1的只有26。数列为26+30N，（4）、把26+30N数列取7项为：26，56，86，116，146，176，206，除以7余6的只有146。数列为146+210N， （5）、把146+210N数列取11项为：146，356，566，776，986，1196，1406，1616，1826，2036，2246，除以11余7的只有986。数列为986+2310N。 因为，986同时满足后面的余数条件，我们就不再推下去了，反正方法是一样的。 2、根据这些余数求偶数的素数对。如果某数与偶数除以素因子的余数相同，那么，该数的对称数必然被素因子整除，能够被该素因子整除的数，必然是含该素因子的合数或该素因子本身。那么，我们就选择既不能被素因子整除的数，也不与偶数除以素因子余数相同的数，组成偶数的素数对。 （1）、不与偶数除以2余0的数相同的数的数列为：1+2N， （2）、把1+2N数列取3项为：1，3，5。除以3不余2，又不余0的数有1，数列为：1+6N，因偶数除以6余2，那么，2-1=1，得1+6N数列的对称数列也为1+6N。 （3）、把1+6N数列取5项为：1，7，13，19，25。除以5不余1，又不余0的数有7，13，19，数列有：7+30N，13+30N，19+30N，因偶数除以5余1，因公差为30，986/30余26，有26-7=19，26-13=13。得7+30N的对称数列为19+30N，13+30N的对称数列为13+30N，（4）、把这三个数列各取7项为： 7+30N有：7，37，67，97，127，157，187， 13+30N有：13，43，73，103，133，163，193， 19+30N有：19，49，79，109，139，169，199。 除以7既不为0，也不余6的有：19，37，43，67，73，79，103，109，127，157，163，

孪生素数

目录 [隐藏] ? 1 序列 ? 2 性质 ? 3 多元组 ? 4 猜测与证明 ? 5 参见 ? 6 外部链接[

?收敛性 ?结构

?定理 ?统计分析 统计分析所有小于 4.35 · 1015的孪生素数，可以得到小于x的素数对的个数是 x·f(x)/(log x)2。当x较小时，f(x) 大约为 1.7，当x较大时大约为 1.3。f(x) 的值和孪生素数常数（twin prime constant）相近： [编辑]多元组 孪生素数的概念可以扩展到多元组，即由多个间隔为2的素数构成的序列。由于三个相邻整数总有一个能被3整除，不可能是素数，因此(3, 5, 7) 是唯一的孪生素数三元组。而且由于更多元素构成的孪生素数多元组必定包含三元组的结构，因此多于三个元素的孪生素数多元组不存在。 [编辑]猜测与证明 1921年，英国数学家哈代和李德伍兹曾猜测，如果：代表不大于x 的孪生素数个数，则有：，其中：

查看 ?条目 ?讨论 ?编辑本页 ?历史 ?大陆简体 ?港澳繁體 ?马新简体 ?台灣正體 个人工具 ?试用测试版 ?登录／创建账户

搜索 导航 ?首页 ?分类索引 ?特色内容 ?新闻动态 ?最近更改 ?随机页面 帮助 ?帮助 ?社区入口 ?方针与指引 ?互助客栈 ?询问处 ?字词转换 ?联系我们 ?关于维基百科 ?资助维基百科工具箱 ?链入页面 ?链出更改 ?上传文件 ?特殊页面 ?可打印版 ?永久链接 ?引用此文 其他语言 ???????? ?Català

??esky ?Dansk ?Deutsch ?Ελληνικ? ?English ?Esperanto ?Espa?ol ?Suomi ?Fran?ais ?????? ?Magyar ?Italiano ?日本語 ???? ?Ripoarisch ?Монгол ?Plattdüütsch ?Nederlands ??N orsk (bokm?l)? ?Polski ?Português ?Русский ?Sloven??ina ?Svenska ?????? ?Türk?e ?Укра?нська ?Ban-lam-gú ?本页面最后修订于2010年2月17日 (星期三) 06:14。 ?本站的全部文字在知识共享署名-相同方式共享 3.0协议之条款下提供，附加条款亦可能应用。（请参阅使用条款） Wikipedia?和维基百科标志是维基媒体基金会的注册商标；维基?是维基媒体基金会的商标。 维基媒体基金会是在美国佛罗里达州登记的501(c)(3)免税、非营利、慈善机构。 ?隐私政策 ?关于维基百科 ?免责声明

素数论文

探索素数之迷挑战世界极限 ―――有关＂素介数＂的初步探索 ０２级工程管理３班陈冬冬０２５５０３０２ 内容摘要：本文在对＂素数＂及其相关问题进行探讨之后，首次提出＂素介数＂＂合介数＂的概念并推导出素介数、合介数的递推公式和奇素数公式，作出相关证明与分析．并应用素介数相关理论对整数进行新的分类、对一些素数猜想进行分析后论证后或初步给出其满足条件和等价命题或对其作出初步不完全证明．最后提出相关推论和猜想． 关键词：素数素介数合介数素数公式哥德巴赫猜想 Explore the prime fan Challenge the limit of the world ---Have something to do with the preliminary exploration that " Prime media " Content summary : This text is after carry on the discussion to " prime " and relevant problems, Put forward “Prime media” and”Count jointly media” concept for the first time and derive out Prime media , Count jointly media and very prime formula and make relevant identifications and analyse. Use Prime media and count relevant theories and carry on the new classification to the integer , to some being prime to is it go on after analysing after proving or provide it meet condition and equivalent proposition or make to it preliminary to prove at all tentatively to guess. Propose relevant inferences and guess finally . Keyword:Prime Prime media Count jointly media Prime formula Goldbach's Conjecture ［引言］： 长期以来，“素数问题”在数学研究尤其是在数论研究中都占据着举足轻重的地位。素数在自然数中的非正态无规律分散着，它的分布规律及其相关问题，令数学家们为之伤透了脑筋。它就象一个顽皮的孩子一样，东躲西藏和数学家们玩起“捉迷藏”的游戏而且一玩就是千百年之久。什么样的自然数才是素数？如何从庞大的自然数集中将素数“揪”出来呢？以及自然数中到底有多少个素数？......这一系列问题一直是困惑数学界的难题。众所周知，在所有素数中，除了2这个唯一的偶素数外，其余的均为奇素数。那么，什么样的奇数才是素数？能否将所有的奇数都统一到一个表达式中呢？哪怕是一个极其抽象的式子。本着此目的，本文将大胆地提出“素介数”的概念并对其进行相关推导和论证，初步给出“孪生素数”、“费马素数”、“默森尼素数”等所满足的条件，并应用相关推论对“哥德巴赫猜想”进行初步分析和给出部分证明，最后提出相关猜想和推论。 １.预备知识及其“素介数”的引入： １.１.相关概念： １.１.１.素数的概念： 素数：也叫质数，是只能被１和它本身整除的自然数。这里记作Ｐi 表示第i个素数。如：２，３，５，７，１１，１３，１７，１９，２３，２９，...... １.１.２.合数的概念： 合数：约数中除了１和它本身外，还有其它约数的自然数。这里记作Ｈk表示第k个和数。如：４，６，８，９，１０，１２，１４，１５，１６，１８，...... 注１：１既不是素数也不是合数。 １.１.３.自然数集合可以分为三大类： 第一类：１（约数只有１）； （约数只有两个）; 第二类：素数P i 第三类；合数H （约数多于两个）; k ２.“素介数”与“合介数”的引入： ２.１.“素介数”的定义：

PAT计算机能力考试乙级1-10题答案教学文稿

1001害死人不偿命的(3n+1)猜想（15 分 对任何一个正整数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展…… 我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？ 分析：输入一个正整数n进行循环，n=1循环截止,判断n,如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1，并计算经过的次数m。 #include"stdlib.h" #include"stdio.h" int main() { int n,m; m=0; scanf_s("%d",&n); while(n!=1) { if(n%2==0) { n=n/2; } else { n=(3*n+1)/2; } m++; } printf_s("%d\n",m); system("pause"); } 1002写出这个数（20 分） 读入一个正整数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。 分析：输入一个正整数n， while循环求出n的各位数字之和sum；如果sum等于0，那么就输出它的拼音”ling”；如果不等于0，输入数组b存放各位数字之和，在switch对这个数组进行判断数组b各个数的数值为多少，0对应"ling"; 1对应"yi";2:对应<"er";3对应"san";4对应"si";5对应"wu";6对应"liu";7对应"qi";8对应"ba";9对应"jiu";

对素数递推公式的推导过程

对素数递推公式的推导过程 山东章丘一职专马国梁 （2011.4.27 新浪博客首发） 前边公布的素数递推公式P i +1 = P i + ( P i - P i -1 ) P i / (P i - 1 ) 它的成立绝不是偶然的，它是由产生素数的核心机制决定的，反映了前后素数的关系。多年来有无数数学家在探索素数规律的问题上，之所以费尽苦心而收效甚微，其原因就是他们一向把所有素数都当成一个整体对待，同时考虑各个素数的作用。而没有考虑其微观机制，前边素数对后边的作用。 事实上，后边素数是由前边所有素数共同作用的结果。前边参与的素数越多，后边生成素数的机会就越少。这就是素数越往后越稀少的原因。 在每个素数P i后边的一段距离内是没有素数的，所以它们可能被sqrt (P i) 和它前边的任何一个素数整除。而按照概率，各素数进行整除的机会是不同的。其中素数越大，它去整除的机会就越少。它们分别是1/2 、1/3 、1/5 ……1/sqrt (P i) 。这样P i后边有限的宽度便被一点一点的削减，当削减到只剩下一个数字的宽度时，新的素数就要产生了。其期望值我们可以根据这个原理算出来。即 因为[P i+1 - P i ][1/2] [2/3] [4/5] ……[(sqrt(P i) – 1) / sqrt(P i) ] = 1 所以P i+1 = P i + [2/1] [3/2] [5/4] ……[sqrt(P i)/(sqrt(P i) – 1) ] = P i +ΔP i 通过数字计算可以证明，当P i很大时，素数宽度 ΔP i = [2/1] [3/2] [5/4] ……[sqrt(P i)/(sqrt(P i) – 1) ] = [3/2] [5/4] [7/6] ……[P i /(P i– 1) ] 且由于ΔP i-1 = [3/2] [5/4] [7/6] ……[P i-1 /(P i-1– 1) ] 所以ΔP i =ΔP i-1 [P i /(P i– 1) ] 故得P i+1 = P i +ΔP i-1 [P i /(P i– 1) ] 又由于ΔP i-1 = P i - P i-1 所以最后得P i +1 = P i + ( P i - P i -1 ) P i / (P i - 1 ) 证毕。 这个公式深刻揭示了素数产生的本质原因，各个素数的作用大小通过概率反映了出来。在这些无规则的数字面前，统计概率论又一次显示了它的强大威力，一匹桀骜不驯的野马终于被一条缰绳制服了。 这个公式还反映了素数数列的一个重要性质：即它是一个振荡的素数宽度不断增大的非等差数列；而相邻素数宽度则又是一个比值渐渐趋于1的非等比数列。两种数列叠加到一块，再加上振荡从而使它表现出了极不规则的性质。

C语言编程题_1

1.素数 1. [100，999] 15 2 [300，800]。761 6.。试求[100,999]之内的所有逆向超级素数的个数。39 3问[31,601]之间有多少对双胞胎数22 5. 求出[200，1000]之间的最大一对双胞胎数的和。1764 4. 试求6744可以分解成多少种不同的素数对144 7.。试求1234可以分解成多少种不同的素数对25 8.求[100，900]之间相差为12的素数对的个数。50 9. 试求[100,999]之内的所有逆向超级素数的和。21645 10.。试求[100,999]之内的所有逆向超级素数从大到小数的第10个素数是多少？797 11. 试求所有两位绝对素数的和。429 12. 在[200，900]范围14 13. 求[100,999]之内超级素数的个数。14 14. 求[100，200]之间的第10个友素数对所对应的友素数的值17291 15. 求[2，400]中相差为10的相邻素数对的对数。 5 16. 求[50，150]之间的友数对的数目。38 17. 求[40,119]之间友素数对的数目。30 18.，求[1，21]范围内有多少个梅森尼数？7 19. [300，800]范围求满足上述条件的最大的三位十进制数。761 20. 求符合下列条件的四位完全平方数. 求其中最大的一个数。7921 21.设某四位数的千位数字：3201， 3^2+0^2=2^3+1^3，试问所有这样的四位数之和是多少？97993 22. 设某四位数的千位数字与十位数字的和等于百位数字与个位数字的积，例如，对于四位数：9512， 9+1=5*2，试问所有这样的四位数之和是多少？1078289 23. 有一个三位数满足下列条件: (1)此三位数的三位数字各不相同; (2)此三位数等于它的各位数字的立方和。试求所有这样的三位数之和。1301 24.求[1，999]之间能被3整除，且至少有一位数字是5的所有正整数的个数。91 25. 有一个三位数满足下列条件: (1)此三位数的三位数字各不相同; (2)此三位数等于它的各位数字的立方和。试求所有这样的三位数中最大的一个是多少？407 26. 有一个三位数满足下列条件: (1)此三位数的三位数字各不相同; (2)此三位数等于它的各位数字的立方和。试求这种三位数共有多少个？ 4 27. 求五位数各位数字的平方和为100的最大的五位数。94111 28. 所谓“水仙花数”是指一个三位数，其各位数字的三次方之和等于该数本身，例如：153=1^3+3^3+5^3，故153是水仙花数，求[100，999]之间所有水仙花数之和。1301 29. 设某四位数的各位数字的平方和等于100，问共有多少个这种四位数？49 30. 回文数是指正读和反读都一样的正整数。例如3773是回文数。求出[1000，9999]以内的所有回文数的个数 31.把一张一元钞票,换成一分、二分和五分硬币,每种至少8枚,问有多少种方案? 80 32. 50元的整币兑换成5元、2元和1元币值（三种币值均有、缺少一种或两种都计算在内）的方法有多少种。146 33. 50元的整币兑换成5元、2元和1元币值（要求三种币值均有）的方法有多少种。106 34. 马克思曾经做过这样一道趣味数学题：试求有多少种方案分配男人、9 35. A,B,C是三个小于或等于100正整数，当满足1/A^2+1/B^2=1/C^2关系时，称为倒勾股数。求 130B>C的倒勾股数有多少组。 1 36. 倒勾股数是满足公式：求A，B，C之和小于100的倒勾股数有多少组？ 2 37. 勾股弦数是满足公式：求A，B均小于25且A+B+C<=100的勾股弦数的个数。11 38. 倒勾股数是满足公式：假定A>B>C，求A，B，C均小于或等于100的倒勾股数有多少组？ 4