高中数学关于素数的知识和算法

用心 爱心 专心 关于质数 素数 的知识和有关算法关于质数 素数 的知识和有关算法 资料来源 维基百科 资料来源 维基百科 素数定义 素数 Prime Number 亦称质数 指在一个大于 1 的自然数中 除了 1 和此整数 自身外 无法被其它自然数整除的数 换句话说 只有两个正因数 1 和自己 的自然数即 为素数 比 1 大但不是素数的数称为合数 1 和 0 既非素数也非合数 素数在数论中有着很重要的地 位 关于素数 最小的素数是 2 也是素数中唯一的偶数 双数 其它素数都是奇数 单数 素数有无限 多个 所以不存在最大的素数 围绕着素数存在很多数学问题 数学猜想和数学定理 著名的有孪生素数猜想和哥德巴赫猜 想 素数序列的开头是这样 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 素数集合有时表示成粗体 在抽象代数的一个分支 环论中 素元素有特殊的含义 在这个含义下 任何素数的加法的 逆转也是素数 换句话说 将整数 Z 的集合看成是一个环 Z 是一个素元素 但是在数学领 域内 提到素数时通常指正的素数 算术基本定理证明每个大于 1 的正整数都可以写成素数的乘积 并且这种乘积的形式是唯一 的 因此素数也被称为自然数的 建筑的基石 例如 素数的数目 素数有无穷多个 现在已知最早的证明方法是欧几里得在他的 几何原本 中提出的 该证 明方法如下 假设素数有限 把所有这些有限的素数相乘以后加 1 可以得到一个数 这个数无法被那些 有限的素数里的任何一个整除 因为无论被哪一个素数除 总有余数 1 如果该数为素数 则根据假设 它不在那些假设的素数集合中 如果该数为合数 因为任 何一个合数都可以分解为几个素数的积 而一开始假设的那些素数都不能整除该合数 所以 该合数分解得到的素因子肯定不在假设的素数集合中 因此无论该数是素数还是合数 都 意味着在假设的有限个素数之外还存在着其它素数 对任何有限个素数的集合来说 用上 述的方法永远可以得到有一个素数不在假设的素数集合中的结论 所以原先的假设不成立 也就是说 素数并非有限 而是有无穷多个 其它数学家也给出了他们自己的证明 恩斯特 库默的证明更为简洁 Hillel Furstenberg 则用 拓扑学加以了证明 尽管整个素数是无穷的 仍然有人会问 100000 以下有多少个素数 一个随机的 100 位 用心 爱心 专心 数多大可能是素数 素数定理可以回答此问题 寻找素数 寻找在给定限度内的素数排列 埃拉托斯特尼筛法是个很好的方法 然而在实际中 我们往 往是想知道一个给定数是否是素数 而不是生成一个素数排列 进而 知道是素数的概率有 多大就是可以了 用素性测试迅速地检查一个给定数 例如 有几千位数的长度 是否是素 数是可能的 典型的方法是随机选取一个数 然后围绕着这个数和可能的素数 N 检查一些方 程式 重复这个过程几次后 它可以基本确定这个数是明显的合数或者可能是素数 这种方 法是不完美的 对某些测试而言 例如费马测试 不论选取了多少随机数都有可能将一些合 数判断成可能的素数 这就引出了伪素数 而像米勒 拉宾测试 虽然只要选取够多的数字来 检验方程式 就可以保证其检验出的素数性是正确的 但这个检验的数量太过庞大 甚至比 试除法所需的 还要多 在有限的时间内只能知道答案正确的机率很高 不能保证一定正确 数学家一直努力找寻产生素数的公式 利用一条定理 可以正确产生所有的素数 参见素数 公式 历史上有许多试验的例子 17 世纪初法国数学家梅森 Mersenne 在他的一个著作 当中讨论了这样一种我们现在称之为梅森素数的素数 Mp 2p 1 本来以为只要 p 是一个素 数 n 2p 1 就会是一个素数 这在 p 3 p 5 p 7 都是正确的 但是 p 11 时 就不是 素数了 目前最大的已知素数是梅森素数 243112609 1 此数字位长度是 12978189 它是 在 2008 年 8 月 23 日由 GIMPS 发现 这组织也在 2008 年 9 月 6 日发现了目前所知第二大的 已知素数 237156667 1 此数字位长度是 11185272 素数算法 欲求出小于 x 的所有素数参见素数公式 检验素数 检查一个正整数 N 是否为素数 最简单的方法就是试除法 将该数 N 用小于等于 的所有素 数去试除 若均无法整除 则 N 为素数 2002 年 印度人 M Agrawal N Kayal 以及 N Saxena 提出了 AKS 素数检验算法 证明了可以 在多项式时间内检验是否为素数 已经证明的定理 在一个数和它的 2 倍之间必存在一个素数 存在任意长度的素数等差数列 格林和陶哲轩 2004 年 一个偶数可以写成两个数字之和 其中每一个数字都最多祇有 9 个质因子 挪威数学 家布朗 1920 年 一个偶数必定可以写成一个质数加上一个合成数 瑞尼 1948 年 一个偶数必定可以写成一个质数加上一个由 5 个因子所组成的合成数 后来 有人简称 这结果为 1 5 中国潘承洞 1968 年 未解之谜 哥德巴赫猜想 是否每个大于 2 的偶数都可写成两个素数之和 孪生素数猜想 孪生素数就是差为 2 的素数对 例如 11 和 13 是否存在无穷多的孪生 素数 斐波那契数列内是否存在无穷多的素数 是否存在无穷多的梅森素数 在 n2 与 n 1 2 之间是否每隔 n 就有一个素数 是否存在无穷个形式如 n2 1 的素数 黎曼猜想 素数的应用 用心 爱心 专心 素数近来被利用在密码学上 所谓的公钥就是将想要传递的信息在编码时加入素数 编码之 后传送给收信人 任何人收到此信息后 若没有此收信人所拥有的密钥 则解密的过程中 实为寻找素数的过程 将会因为找素数的过程 分解质因数 过久 使即使取得信息也 会无意义 在汽车变速箱齿轮的设计上 相邻的两个大小齿轮齿数最好设计成素数 以增加两齿轮内两 个相同的齿相遇啮合次数的最小公倍数 可增强耐用度减少故障 在害虫的生物生长周期与杀虫剂使用之间的关系上 杀虫剂的素数次数的使用也得到了证明 实验表明 素数次数地使用杀虫剂是最合理的 都是使用在害虫繁殖的高潮期 而且害虫很 难产生抗药性 以素数形式