数学实验之二---素数.ppt

数学实验之五 --- 素数 实验内容 素数的个数 素数表的构造 素数的判别 最大的素数 求解素数的公式 素数的分布 1、素数的个数 算术基本定理：任何整数都可以分解为 设 为所有的素数。考察 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年编织出内的素数表。 试除法 假设我们已经找到了前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。 3、素数的判别 威尔逊判别法 n是素数的充要条件是 这里 是指 a-b 被p整除。 不过该算法的运算量为O(nlogn^2),计算量太大。 4、最大的素数 Mersenne数 形如 的数称为Mersenne数。利用Mersenne数可以构造出非常大的素数。 很显然，如果n是合数，则M_n也为合数，但n为素数时，M_n不一定为素数。例如，M_11=2047=23x89是合数。 5、生成素数的公式 是否存在单变量整系数的多项式, 它只生成素数并且生成所有的素数? 更一般地,是否存在一个生成素数的多变量函数公式? 如果这样的公式不存在, 能否找到一个虽不能给出全部但能给出无穷多个素数(且只给出素数)的公式? 6、素数的分布 素数沿数轴的分布 （1）随着整数范围的扩大，素数是不是越来越稀疏？稀疏的程度是否单调地增加？ （2）相邻素数之间的间隔值有哪些? 它们各重复多少次? 哪些间隔值的重复次数多? 最大间隔值是多少? 随整数范围扩大, 最大间隔值是否也随之增大? 7、 进一步的思考问题 Goldbach 猜想 Goldbach于1742年给大数学家Euler的信中提出了两个猜想, 即每个不小于6的偶数都可以表为两个奇素数之和; 每个不小于9的奇数可以表为三个奇素数之和. Euler在随后的复信中写道: 任何不小于6的偶数都是两个奇素数之和, 虽然我不能证明它, 但我确信无疑这是完全正确的定理. 这就是著名的Goldbach猜想的由来. 完全数 所谓完全数是指它的所有因子(除去它本身 ) 之和等于该完全数. 例如, 6是一个完全数. 因为1+2+3=6. 下一个完全数是28. 请读者找出10000以内的所有完全数, 并对它做素因子分解. 你能据此猜测完全数的通式吗? 完全数与Mersenne素数有何联系? 你能由此找到更多的完全数吗? 是否存在奇完全数? 完全数是否有无穷多个? 除6以外, 完全数都有一个奇妙的特性, 就是每个完全数可以表为几个连续的奇数之立方和. 如28=1^3+2^3. 请你对你找出的完全数验证此特性. 完全数的另一个特性是它的因子的倒数和为1。如 1/2+1/3+1/6=1。 把完全数（除6）各位数相加得另一数，这样一直做下去，最后得1。 完全数二进制形式为：11…100…0 孪生素数 间隔为2的相邻素数，如3与5，5与7。关于孪生素数的猜想是：孪生素数有无穷多个。 1919年，挪威数学家布隆考虑孪生素数的倒数和： 如果上述数列发散，则孪生素数有无穷多个。遗憾的是，上述数列收敛，其和为B=1. 用p(x)表示不超过x的孪生素数的个数。英国数学家Hardy与Littlewood猜测 其中 迄今为止，孪生素数猜想还没有证明。目前最好的结果是我国数学家陈景润于1966年获得：存在无穷多个素数p, 使p+2是不超过两个素数的乘积。截止1999年发现的最大孪生素数是 青一色数的素性 由n个1组成的数11...1叫做青一色数. 当n为何值时, 青一色数是素数? 如果青一色数是合数, 如何将它做素因子分解? 很显然，如果n为合数，则清一色数为合数。目前只得到n=2,19,23,317,1031时，清一色数为素数。 Bertrand猜测 当n3时, n与2n-2之间至少存在一个素