数学实验之五-素数 中国科学技术大学数学系 陈发来 13466917
数学实验之五 --- 素数 中国科学技术大学数学系 陈发来 2 1 13466917 −
险内容 素数的个数 素数表的构造 素数的判别 最大的素数 求解素数的公式 素数的分布
实验内容 素数的个数 素数表的构造 素数的判别 最大的素数 求解素数的公式 素数的分布
1、素数的个数 算术基本定理:任何整数都可以分解 为 n=p1 p2.pk 设p1,p2…,Pn为所有的素数。考察 N=nP2…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必以某些P为因子 这是不可能的! 虽然素数有无穷多个,但随着整数范围 越来越大,素数似乎越来越稀少 1,100]-25 [0001100-16 [1000100100]-6 [100000000100]-2
如果N为合数，则N必以某些 为因子。 这是不可能的！ 虽然素数有无穷多个，但随着整数范围 越来越大，素数似乎越来越稀少。 [1，100]----25 [1000,1100]---16 [100000, 100100]---6 [10000000,10000100]---2 i p
素数表的构造 Eratosthenes筛法 3456789 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以内的素数表