素数公式

在计算机科学中，素数公式是一种算法 f ( n ) ，这样对于自然数 n  值 f ( n )  n - 第 一个素数。 在数学，尤其是数论中，这对应于提供大量素数的公式（素数公式）。 到目前为止，还没有找到更高效的素数公式，尤其是没有切实可行的生成素数的封闭公式。

但是，有些公式生成的数有一定的概率是素数，所以生成的数还是要检验一下是不是素数。 本文还讨论了其他不实用但已在数学文献中讨论过它们是否会产生许多素数的公式。

确定素数的最古老的算法之一是埃拉托色尼筛法，在该算法中，这些数字从自然数列表中一个接一个地删除，这些数字是尚未删除的最小数的倍数。 这将素数留在初始列表中。

欧拉已经给出了公式 n 2 + n + 17和 n 2 − n + 41 ，对于 0 ≤ n < 16 或 0 ≤ n <; 41 返回素数。 即使对于更大的 n值，这两个公式也会返回许多质数，因为结果永远不会被质数 p <; 17  或 p 4没有这样的素数。

根据狄利克雷素数定理，一个等差数列包含 a ⋅ m + b，无穷多个素数（也包括合数）。对于每个 k都有算术序列，产生 k 连续值的素数。

一个平凡的素数公式可以归纳地定义如下：

• f ( 1 ) = 2
• f ( 2 ) = 3
• 对于 n ≥ 2  是 f ( n ) 之后的质数，其中f ( n ) + 2 中的所有数字按升序进行素数测试是。

然而，这种方法非常低效，因为所有奇数自然数都必须一个接一个地进行测试。 作为替代方案，建议使用筛分方法，例如埃拉托色尼筛法或阿特金筛法，创建一个足够长的素数列表，然后遍历该列表直到达到所需的素数。 这样做时，有时首先要确定与素数（几乎是素数）相似的数量。

所有素数的一个不太实用的公式是基于威尔逊定理的。

如果你对单个变量使用自然数，当且仅当不等式满足时， k + 2 是质数。

还有一个 n 丢番图方程组，它只用十个变量生成素数（而且只有这些），但次数非常高，人们总能找到这样一个最多只有四次多项式的系统，但在这种情况下，变量的数量非常多。 到目前为止，这些方法还没有任何实际用途。