中国科学技术大学：《数学实验》课程教学资源（实验讲稿PPT）实验五 素数（陈发来）

数学实验之五一素数 中国科学技术大学数学系 陈发来 23465911

数学实验之五 --- 素数 中国科学技术大学数学系 陈发来 2 1 13466917 −

内容 素数的个数 素数表的构造 素数的判别 最大的素数 求解素数的公式 素数的分布

实验内容 素数的个数 素数表的构造 素数的判别 最大的素数 求解素数的公式 素数的分布

1、素数的个数 算术基本定理:任何整数都可以分解 为 n= p 设p12P2,…,Pn,为所有的素数。考察 N=P1P2…Pn+1

1、素数的个数 • 算术基本定理：任何整数都可以分解 为 • 设 p1 , p2 ,  , pn 为所有的素数。考察 N = p1 p2 pn +1 dk k d d n p p p 1 2 = 1 2

如果N为合数,则N必以某些P1为因子。 这是不可能的 虽然素数有无穷多个,但随着整数范围 越来越大,素数似乎越来越稀少。 [1,1001-25 [000100-16 00001001001-6 10000000100001001-2

如果N为合数，则N必以某些 为因子。 这是不可能的！ 虽然素数有无穷多个，但随着整数范围 越来越大，素数似乎越来越稀少。 [1，100]----25 [1000,1100]---16 [100000, 100100]---6 [10000000,10000100]---2 i p

素数表的构造 Eratosthenes筛法 23456789 10 11121314151617 181920212223242526 27282930313233 经过众多学者的艰辛努力, D.N. Lehmer于 1914年编织出了10000000内的素数表

2、素数表的构造 • Eratosthenes筛法 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 31 32 33 经过众多学者的艰辛努力, D.N.Lehmer 于 1914年编织出了10000000以内的素数表

试除法 假设我们已经找到了前n个素数p1=2 p2=3…pn,为了寻找下一个素数我们 从pn+2开始依次检验每一个整数N看N 是否能被某个pii=1,2…n整除如果N 能被前面的某个素数整除,则N为合数否 则N即为下一个素数p{n+1} 为提高算法的效率,只需用不超过√的 素数去除N

• 试除法 假设我们已经找到了前n个素数p_1=2, p_2=3, ...,p_n, 为了寻找下一个素数我们 从p_n+2开始依次检验每一个整数N, 看N 是否能被某个p_i, i=1,2,...,n整除. 如果N 能被前面的某个素数整除, 则N为合数. 否 则N即为下 一个素数p_{n+1}. 为提高算法的效率，只需用不超过 的 素数去除N。 N

3、素数的判别 威尔逊判别法 n是素数的充要条件是 (n-1)!+1≡0(modm) 这里a≡ b mod p是指a-b被p整除 不过该算法的运算量为 o(nlogn^2)计 算量太大

3、素数的判别 威尔逊判别法 n是素数的充要条件是 这里 是指 a-b 被p整除。 不过该算法的运算量为O(nlogn^2),计 算量太大。 a  b mod p (n −1)!+1  0 (mod n)

Fermat判别法 如果p是素数,a与p互素,那么 a=l moa p 实际上,大约2500年前,中国古代数学家 就发现了上述结论。他们由此得出:如 果2”=2(删n边素数。该判别法 的运算量为Oog^3n)

• Fermat判别法 如果p是素数，a与p互素，那么 实际上，大约2500年前，中国古代数学家 就发现了上述结论。他们由此得出：如 果 ,则n为素数。该判别法 的运算量为O(log^3n). a p p 1 mod 1  − 2  2 (mod 2) n

通过编程计算发现,反过来结论并不成 立。例如, 2340=1mod341 但是341=11×34为合数!称使得 2P-=1 mod p 成立的p为伪素数

通过编程计算发现，反过来结论并不成 立。例如， 但是341=11x34为合数！称使得 成立的p为伪素数。 2 1 mod 341 340  p p 2 1 mod 1  −

注意同余的计算: 2=(2 10、34 =102434= (3×341+1)=1mod341 进一步,伪素数有多少个?

注意同余的计算： 进一步，伪素数有多少个？ (3 341 1) 1 mod 341 2 (2 ) 1024 34 340 10 34 34  +  = = =