换句话说，素数不能用小于自身（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年曾用计算机计算出510 ^90位的孪 生素数[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 / n ^s ) = 1 + 1/2 ^s +1/3 ^s + 1/4 ^s + … ，
用ζ(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）数 ¹ 07前后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的10 ³ 大约增加7个。

(2 ^M -1)为素数，称为“梅森数”。

2006年9月4日，(2 ^32,582,657 - 1)被报道为9808358位素数的新候选数。 http://ja.wikipedia.org/wiki/梅森数 。

（4）梅森数(26 ⁷ - 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算法进行模拟运算，也可以充分发挥其特性。
素数的世界正在不断扩展。

渡边 胜正