素数

如何寻找小质数

有一种简单的方法可以找到素数的清单。Eratosthenes创造了它。它的名字叫埃拉托塞尼的筛子。它捕捉非质数（像一个筛子），让质数通过。

这个方法是通过一个数字列表和一个叫做b的特殊数字来实现的，这个数字在方法过程中会发生变化。当你通过这个方法时，你在列表中圈出一些数字，并划掉其他数字。每个圈起来的数字都是质数，每个划掉的数字都是合数。在开始时，所有的数字都是普通的：没有被圈起来，也没有被划掉。

方法总是一样的。

1. 在一张纸上，写下从2到被测试数字的所有整数。不要写下数字1。进入下一个步骤。
2. 从b等于2开始，进入下一个步骤。
3. 在列表中圈出b。进入下一个步骤。
4. 从b开始，在列表中再数b，然后划掉这个数字。重复数出更多的数字和划掉数字，直到列表的最后。进入下一个步骤。
• (例如。当b为2时，你将圈出2并划掉4、6、8，等等。当b为3时，你将圈出3并划掉6、9、12，等等。6和12已经被划掉了。再把它们划掉）。
5. 将b增加1，进入下一步骤。
6. 如果b已经被划掉了，回到上一步。如果b是列表中未被划掉的数字，进入第三步。如果b不在列表中，进入最后一步。
7. (这是最后一步。）你已经完成了。所有的质数都被圈起来了，所有的合数都被划掉了。

举个例子，你可以在一个从2到10的数字列表上使用这个方法。最后，数字2、3、5和7会被圈起来。它们是质数。4、6、8、9和10将被划掉。它们是复合数。

这种方法或算法在寻找非常大的素数时需要太长时间。但它没有用于非常大的素数的方法那么复杂，比如费马的素数检验（检验一个数字是否是素数）或米勒-拉宾的素数检验。

素数是用来做什么的

质数在数学和计算机科学中非常重要。以下是一些现实世界中的用途。非常长的数字是很难解决的。很难找到它们的质因数，所以大多数情况下，可能是质因数的数字被用于加密和秘密代码。

• 大多数人都有一张银行卡，他们可以使用自动取款机从自己的账户中取钱。这张卡是由一个秘密的访问代码保护的。由于该代码需要保密，所以不能以明文形式存储在卡上。加密被用来以秘密的方式存储代码。这种加密使用乘法、除法和寻找大素数的余数。一种叫做RSA的算法在实践中经常被使用。它使用中国余数定理。

• 如果某人的电子邮件有一个数字签名，就会使用加密技术。这确保没有人可以伪造他们的电子邮件。在签名之前，会创建一个信息的哈希值。然后将其与数字签名结合起来，产生一个签名的信息。使用的方法与上述第一种情况大致相同。

• 寻找迄今为止已知的最大素数已经成为一种运动。如果一个数字很大，测试该数字是否为素数是很困难的。任何时候已知的最大素数通常是梅森素数，因为已知最快的素数测试是Lucas-Lehmer测试，它依赖于梅森数的特殊形式。这里有一个寻找Mersenne素数的小组[1]。