|
|
这里，笨人仅打算介绍一些笨人所知的关于素数的一些知识，绝不希望因此引起人们骑自行车上月球的冲动。
厄拉多塞(Eratosthenes)筛法：
按顺序写出有限项自然数数列：2, 3, 4, ..., N-1, N.
2 是素数，保留。从 2 开始数，每 2 位划掉一个数。即，2, 3, 4/, 5, 6/, 7, 8/, 9, 10/, 11, 12/, ...
找到下一个没被划掉的数 3，从 3 开始数，每 3 位（包括已划掉的数）划掉一个数。即，2, 3, 4/, 5, 6//, 7, 8/, 9/, 10/, 11, 12//, ...
找到下一个没被划掉的数 5，从 5 开始数，每 5 位（包括已划掉的数）划掉一个数。即，2, 3, 4/, 5, 6//, 7, 8/, 9/, 10///, 11, 12//, ...
重复以上过程，直到下一个没被划掉的数 p > sqrt(N) 为止。这时，数列中没被划掉的数就是该有限项自然数数列中的全部素数。
但是，厄拉多塞筛法不能用于无限数列，而人们已经证明，素数有无穷多个。
梅森(Mersenne)数和梅森素数:
设 p 是素数，则形如 Mp = 2^p - 1 的数称为梅森数，若 Mp 为素数，Mp 为素数时又称其为梅森素数。前10个梅森素数所对应的 p 依次为 2, 3, 5, 7, 13, 17, 19, 31, 61, 89.
费马(Fermat)数和费马素数:
形如 Fn = 2^(2^n + 1) 的数称为费马数，Fn 为素数时又称其为费马素数。迄今只知5个费马素数：F0=3, F1=5, F2=17, F3=257, F4=65537, F5=4294967297.
伪素数：
设 n, b 属于正整数, n 和 b 的最大公约数 (n,b)=1, n 为合数。若 b^(n-1) == 1 mod n, 则称 n 为以 b 为底的伪素数。
这里用符号 == 表示 “恒等于”的符号。若 a mod p = b mod p, 则记为 a == b mod p. 因此, b^(n-1) == 1 mod n 意为 b^(n-1) mod n = 1 mod n.
已经证明有无穷多个以 2 为底的伪素数。
若 p 是素数，且 b 不能被 p 整除，则 b^(p-1) == 1 mod p, 反之则未必。
米勒(Miller)测试：
设 n 属于正整数, n-1 = 2^s * t, s 属于正整数, t 是奇数, (n,b)=1. 若 b^t == 1 mod n 或 b^(2^j * t) == -1 mod n (1 <= j <= s-1), 则称 n 通过以 b 为底的米勒测试。
若 n 是素数，且 b 不能被 n 整除，则 n 通过以 b 为底的米勒测试，反之则未必。
强伪素数：
若合数 n 通过以 b 为底的米勒测试，则称 n 是以 b 为底的强伪素数。
强伪素数十分罕见，但却有无穷多个。以 2 为底的最小强伪素数是 2047, 以 2 和 3 为底的最小强伪素数是 1373653, 以 2, 3 和 5 为底的最小强伪素数是25326001, 以 2, 3 , 5 和 7 为底的最小强伪素数是 3215031751.
所以，如果你想出了一个素数的计算公式，它是真是伪，需要实践的检验，而证明它是假的素数计算公式，相对比较容易些，只要找出一个反例就可以了。这里说的“比较容易”其实并不容易，但计算机可以为我们寻找。如果目前的计算机尚不能胜任，那么，祝贺你，即使它可能是个假的素数计算公式，你也可以为此而载入史册了，但前提是要经得起公众的检验。MK的特点之一就是他的成果无法公开，接受公众的检验。
参考文献
《现代数学手册》经典数学卷第15篇，华中科技大学出版社，2000年12月 |
|
发表于 2007-2-6 11:01:12
发表于 2007-2-6 12:09:45
发表于 2007-2-7 11:31:36
发表于 2007-2-7 11:37:57
AUSE");/*用系统调用执行PAUSE命令，等待用户按任一键退出*/
