需要有关实现素数 6n-+1 算法的解释吗？

Question

我一直在探索 c 中的素数算法，直到我偶然发现了这个算法，哦，天哪，这个算法真的很快，知道它在 2 之后实现素数的 6n-+1 属性来找到下一个最近的素数，但是我仍然没有得到代码的某些部分，首先为什么考虑到他从 2,3 开始，如果它们分别出现 returns true，下一个条件的用途是什么 if (nb % 2 == 0 || nb % 3 == 0) return FALSE; ?，除 2 和 3 之外，其他所有素数都不能被 2 和 3 整除，并且据说 while 会进行检查，那么 if 条件有什么用？其次，我所说的 while 循环应该实现 6n-+1 属性但我真的没有看到循环中数学表达式和测试表达式之间的相关性？最后，while 中的两个条件似乎很可爱且数学化，但我并没有那么多地使用它们，请你澄清一下。非常感谢。

#include <stdio.h>
#define TRUE 1
#define FALSE 0
int is_prime(int nb)
{
    int divisor;

    if (nb == 2 || nb == 3)
        return TRUE;
    if (nb % 2 == 0 || nb % 3 == 0)
        return FALSE;
    divisor = 6;
    while (divisor * divisor - 2 * divisor + 1 <= nb)
    {
        if (nb % (divisor - 1) == 0)
            return FALSE;
        if (nb % (divisor + 1) == 0)
            return FALSE;
        divisor += 6;
    }
    return (1);
}

int find_next_prime(int nb)
{
    while (!is_prime(++nb))
    {};
    return nb;
}
int main()
{
    printf("%i", find_next_prime(78314683));
    return (0);
}

Answer 1

首先，如果数字是 2 和 3，则代码 return 为真，因为它们是质数。 if (nb % 2 == 0 || nb % 3 == 0) 用于丢弃所有可以被 2 或 3 整除的数字（除了 2 和 3 之前已被接受为质数），因为它们显然不是质数。此条件对于正确测试小 nb 值是强制性的。实际上，while 循环以 divisor 设置为 6 开始，因此 divisor * divisor - 2 * divisor + 1 = 25 意味着 nb 必须大于或等于 25，以便执行循环的一次迭代。请注意，选择 25 是因为所有不是素数的较小数字都可以除以 2 或 3，而前面的条件可以捕获所有这些。

关于主循环，想法是当一个数字大于 6 时，只有数字 nb=6k+1 和 nb=6k-1 可以是（但不是必需的）质数。事实上，nb=6k+0 可以被 6 除，nb=6k+2 可以被 2 除，nb=6k+4 和 nb=6k+3 可以被 3 除。剩下的是 nb=6k+1 和 nb=6k+5。后者可以改写为 nb=6k-1 不同的 k.

该算法是对迭代 2 到 sqrt(nb) 之间所有可能数字以找到除数的算法的简单优化。这种优化是可能的，因为不需要检查所有除数，而只需要检查素数。

Answer 2

我真的不认为有关于此算法的证据，但它在某种程度上是独特且棘手的。如果你查看素数序列，你会发现两个连续的最大相差6，这可能是 divisor = 6 和 divisor += 6 的思想。但关键是没有关于素数序列的行之有效的规定。所以也许它不能在大量的情况下正常工作。他使用的另一个无法再次证明的可爱技巧是 6k+1 和 6k-1 中至少有一个是质数。对于 Sieve 来说，这是一个不错但不太强大的优化。显然，这不是您可以在那里找到的最快的素数算法，但也许您会发现它的技巧对其他问题很有用。

Answer 3

让我们从一些理论开始。

第一，n % prime == (n % (prime * anything)) % prime.

这意味着这些都是正确的：

n % prime1 == (n % (prime1 * prime2)) % prime1
n % prime2 == (n % (prime1 * prime2)) % prime2

temp = n % (prime1 * prime2)
n % prime1 == temp % prime1
n % prime2 == temp % prime2

让我们选择质数2和3：

temp = n % 6
n % 2 == temp % 2
n % 3 == temp % 3

temp只有 6 个可能的值:

0, divisible by both 2 and 3
1, not divisible by either 2 or 3
2, divisible by 2
3, divisible by 3
4, divisible by 2
5, not divisible by either 2 or 3

这就是“6n-+1属性”。请注意，2 可被 2 整除，3 可被 3 整除，因此对于这两种情况，我们需要额外检查以确定“可被 2 或 3 整除”是否真的意味着“是质数 2 或 3”（或者它是否是质数意思是“不能是质数”）。

但是……为什么到此为止？

如果有 3 个质数，展开起来很简单：

temp = n % (prime1 * prime2 * prime3)
n % prime1 == temp % prime1
n % prime2 == temp % prime2
n % prime3 == temp % prime3

让我们选择质数 2、3 和 5：

temp = n % 30
n % 2 == temp % 2
n % 3 == temp % 3
n % 5 == temp % 5

现在 temp 有 30 个可能的值:

0, divisible by 2, 3 and 5
1, not divisible by either 2, 3 or 5
2, divisible by 2
3, divisible by 3
4, divisible by 2
5, divisible by 5
6, divisible by both 2 and 3
7, not divisible by either 2, 3 or 5
8, divisible by 2
9, divisible by 3
10, divisible by 2 and 5
11, not divisible by either 2, 3 or 5
12, divisible by both 2 and 3
13, not divisible by either 2, 3 or 5
14, divisible by 2
15, divisible by 3 and 5
16, divisible by 2
17, not divisible by either 2, 3 or 5
18, divisible by both 2 and 3
19, not divisible by either 2, 3 or 5
20, divisible by 2 and 5
21, divisible by 3
22, divisible by 2
23, not divisible by either 2, 3 or 5
24, divisible by both 2, 3 and 5
25, divisible by 5
26, divisible by 2
27, divisible by 3
28, divisible by 2
29, not divisible by either 2, 3 or 5

我们可以将30种可能性打包成30位，得到常量0x208A2882；然后使用 if( (0x208A2882ULL & (1 << n%30)) != 0) /* Not divisible by 2, 3 or 5 */.

但是……为什么到此为止？

如果您选择 2、3 和 7，则需要 42 位（对于 n%(2*3*7) 的 42 种可能性）并且可以使用 uint64_t 常量；如果您选择 5 和 11，则需要 55 位并且可以使用不同的 uint64_t 常量；因此，使用 2 个常数，您可以确定“可被 2、3、5、7 或 11 整除”。

但是……为什么到此为止？

你没有理由不选择 2、3、5、7、11 和 13；并执行 temp = n % (2*3*5*7*11*13) 并有一个大的（30030 位）位域而不是单个整数常量。

但是……为什么到此为止？

对于很多情况（您的 find_next_prime(int nb)），单个“is/isn不可整除”标志很好，但是“下一个不可整除的整数的偏移量”将是好多了，因为你可以一次完全跳过很多数字。您可以执行以下操作：

int find_next_prime(int nb)
{
    do {
        if(nb > 13) {
            nb += table[nb % 30030];
            /* nb is not divisible by 2, 3, 5, 7, 11 or 13 */

Answer 4

is_prime() 对所有 int.

功能不正确

对速度的关注往往无法提供正确的功能。

最好先获得正确的功能，然后再考虑速度。

小值

is_prime() 报告 1 是素数。

代码无法处理小 nb。简单修复：

// if (nb == 2 || nb == 3)
//    return TRUE;
if (nb <= 3) {
  return nb == 2 || nb == 3;
}

大值

is_prime(primes near INT_MAX)（例如 2147483647 或其他）在为质数时被报告为 非质数。这是由于 divisor * divisor.

的整数溢出（未定义行为）

潜在修复：

  divisor = 6 - 1;
  while (divisor <= nb / divisor) {
    if (nb % (divisor - 1 + 1) == 0)
      return FALSE;
    if (nb % (divisor + 1 + 1) == 0)
      return FALSE;
    divisor += 6;
  }

考虑 div() 进行第一次 nb / divisor、nb % (divisor - 1 + 1) 计算。

需要有关实现素数 6n-+1 算法的解释吗？

needed explanation about implementing the 6n-+1 algorithm for primes?

c

algorithm

performance

primes