素数的特征
素数是一种神奇的数字。曾有很多人痴迷于素数，并在数学领域取得了众多成就。
关于这些人士的成就细节，在书籍1和书籍2中有介绍。
素数（p）是只能被正约数“1和自身（p）”整除的数字。
素数没有正约数以外的约数即“真约数”，没有p=1×p以外的因数形式。
换句话说，素数不能用小于自身（p）的数的乘积来表示。另一方面，将素数组合起来，能够成为其他任何数字的基础。
素数是表现京都计算机学院和京都情报大学院大学标语“No.1 & the Only One”的数。
素数只能被自身整除，表示“the Only One”。
另外，在{素数p和大于p的素数}乘积形成的数组之中，p是最小的数字，即素数是“No.1”的数字。
例如，素数p= 41只能被41整除，它是数组{41、41×41、41×43、41×47、41×53，...}中的第一个数字。
这意味着，素数始于理解自身及自身数组。另外，素数还在确定大于自身的数字“是否为素数”方面发挥着作用。
求素数
找出所有小于数字N的素数的方法之一是“埃拉托色尼筛选法”。它的步骤如下所示。
1. 使用位数组pr[1:N]表示小于N的素数的候选项。初始值全部为ON（1）。
2. 从数p=2开始，设p所有倍数的pr值为OFF（0），将其从素数候选项中剔除。
3. 重复第2步，直到数p为(p×p) > N。
4.pr值为ON（1）的数字为小于数N的素数。
比如，N=100之前有25个素数。
{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}
在素数中，一对值相差2的素数称为孪生素数。
数N=100之前有6对孪生素数。
[11, 13] [17, 19] [29, 31] [41, 43] [59, 61] [71, 73]
特别是，[41和43]这对数让人觉得“好记”。
稍大点的孪生素数有[1,000,037, 1,000,039]。
而且，据报道2002年曾用计算机计算出51090位的孪生素数[33,218,925×2169,690±1]。[3, p.33]
素数相关公式存在吗
现在，为什么要使用“埃拉托色尼筛选法”或基于该法的方法？
这是因为我们尚未找到解决以下两点的公式或计算式。
问题1. 数N之前有多少个素数？π(N)
问题2. 从数2开始数，第K个素数是什么？prime[K]
为了解决这个问题，许多人尝试过，并为诸多数学概念做出了贡献[1, 2]。数列、无限级数、与e和π的关系、对数和黎曼Zeta函数 [1,p107]。
Zeta函数定义为ζ(s) = Σn=1∞ (1 / ns) = 1 + 1/2s +1/3s + 1/4s + … ，
用ζ(2) = π2 / 6 表示 [1, p.93]。
根据黎曼（Riemann）推测“是否存在表示小于数N的素数个数的通用规则或公式？”[2, p.15]，得出一个黎曼猜想“zeta函数的所有非平凡零点的实部都是1/2”[2，p.17]。
这个问题到现在依旧没有解决。
作为一种近似解决方案，据说下列素数定理及其结果被认为很不错[2，p70-71]。
素数定理：π(N) ～ N / log N （标记“～”表示近似）
由素数定理得到的结论：
N是素数的概率为 ～ 1 / log N
第K个素数 ～ K log K
计算机的作用
计算机对素数计算和素数性质验证做出了重要贡献。
例如，人们导出了以下趋势和结果：
（1）数107前后100 内的素数个数不同。[1, p.16]
9,999,901 907 929 931 937 943 971 973 991（前面9个）
10,000,019 079 （后面2个）
（2）数N前面的素数个数π(N) 与素数的平均间隔（N /π(N)）。
[1, p.77 & p.137][2, p.60 & 64]
平均间隔为，每个N的103大约增加7个。
| N | π(N) | 平均间隔 |
| 109 | 50,847,534 | 19.6666 |
| 1012 | 37,607,912,018 | 26.5901 |
| 1015 | 29,844,570,422,669 | 33.5069 |
| 1018 | 24,739,954,287,740,860 | 40.4204 |
反过来，求第K个素数prime[K]。这个是1字32位的范围，不久前才求出。现在，我们可以在更短的时间内找求出结果。
| K | Prime[K] | 计算时间 秒 |
| 105 | 1,299,721 | 06.584 |
| 106 | 15,485,867 | 0176.025 |
| 107 | 179,424,691 | 4927.973 |
| 99,940,770 | 2,036,804,591 | 141410.812 (39.28小时) |
1字64位的范围又怎么计算呢？大家不妨试一试。
（3）2005年2月18日，德国发现(225,964,951 - 1)为7816230位素数。 [1, p.315]
(2M -1)为素数，称为“梅森数”。
2006年9月4日，(232,582,657 - 1)被报道为9808358位素数的新候选数。 http://ja.wikipedia.org/wiki/梅森数。
（4）梅森数(267 - 1) 表示两个素数的乘积193,707,721 × 761,838,257,287。（1903年）[1,p.336]
该结果发展成为基于两个素数（P，Q）乘积的RSA加密系统（Ron Rivest，Adi Shamir，Leonard Adleman，1997年）。
这是基于：算出P和Q的乘积M容易，反过来很难将大数M分解为两个素数。这里使用的是模运算（modulo）。
RSA作为公钥加密方法之一而闻名（1976年，Whitfield Diff & Martin E. Hellman）。[1, p341]
量子计算的发展
RSA的核心是大数N的因式分解需要很长时间。
然而，科学家们提出一种“Shor量子因式分解算法”，或许可以通过使用量子计算机的量子计算在短时间内解决。这个算法利用了模运算的周期性和量子计算的叠加性质。
利用当前计算机对Shor算法进行模拟运算，也可以充分发挥其特性。
素数的世界正在不断扩展。
- [1] Marcus du Sautoy, The Music of the Primes, 2003,
- Marcus・du・Sautoy著（冨永 星 译）,
素数音乐, 新潮社, 2005年8月30日，2,400日元 - [2] John Derbyshire, Prime Obsession, 2003,
- John Derbyshire著（松浦俊辅 译）,
迷上素数的人们, 日经BP社, 2004年8月30日，2,600日元. - [3] Keith Devlin, The Millennium Problems, 2002,
- Keith・Devlin著（山口纯一 译）,
兴奋的数学, 岩波书店, 2004年8月25日, 2,940日元.
渡边 胜正