数学实验之五一素数 中国科学技术大学数学系 陈发来 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以内的素数表