如何列出所有性感素数对

Question

我如何编写一个程序来列出 n 个数中存在的所有性感素数对。
例如，如果 n = 10，则输出应为 (5, 11) 和 (7, 13)

我的想法是生成 n 内的所有素数，然后将每个素数加 6 并检查 i + 6 是否为素数。但是不行，没有输出，程序结束。

#include <stdio.h>

int main() {
    int i, j, n, k, isprime = 1, prime2, flag = 0;
  
    scanf("%d", &n);
          
    for (i = 3; i <= n; i++){
      for (j = 2; j <= i; j++){
        if (i % j == 0)
          break;
      }

      if (i == j){
        prime2 = i + 6;
        for (k = 3; k <= prime2; k++){
          if (prime2 % k == 0){
            flag++;
            break;
          }
        }

        if (flag == 0){
          printf("%d %d\n", i, prime2);
        }     
      }
    }

  return 0;
}

关于我做错了什么的任何想法或关于如何解决它的任何提示？（仅限循环）

Answer 1

您可以使用 Sieve 来加速程序。它可以在 O(N log N) 时间内生成所有对。这是 Algorithm.

现在，您有一个布尔数组 is_prime，其中如果 i 是质数，则 is_prime[i] 为真，否则为假。

现在，从i = 1迭代到i = N并检查是否is_prime[i] && is_prime[i + 6]，如果条件为真，输出对。

Answer 2

由于有很多关于寻找质数的资源，我不打算讨论这个。相反，我会尝试指出您代码中的错误。

第一个问题：

for (k = 3; k <= prime2; k++)

这里你需要运行循环直到prime2 - 1。此外，您应该从 2 而不是 3 开始检查，就像您之前所做的那样。也就是说，

for (k = 2; k < prime2; k++)

或

for (k = 2; k <= prime2 - 1; k++)

原因：当k = prime2时，prime2 % k将是0。为了确定一个数字是否为素数，我们不需要检查该数字是否可以被 1 和该数字本身整除。

注意：现在您可能会想为什么 (j = 2; j <= i; j++) 的第一个素数循环有效。

之所以有效，是因为您在其后给出了附加条件 if (i == j)。

第二题：

您需要在第一个循环中声明 flag 变量。

for (i = 2; i <= n; i++)
{
    int flag = 0;
    .... (rest of the code)
    ....
}

原因： 基本上用 flag 值，你试图找出 prime2 是否是素数。

每次你从第一个循环中得到一个素数，你就会得到一个新值 prime2。在您的代码中，一旦您增加了 flag 的值，就永远不会重置 flag 值。

这就是为什么一旦您的代码检测到 prime2 不是素数，它就永远不会再检测到第二个素数（prime2 实际上是素数）。

总代码：

#include <stdio.h>

int main()
{
    int i, j, n, k, isprime = 1, prime2;

    scanf("%d", &n);

    for (i = 3; i <= n; i++)
    {
        int flag = 0;    //  changing point
        for (j = 2; j <= i; j++)
        {
            if (i % j == 0)
                break;
        }

        if (i == j)
        {
            prime2 = i + 6;

            for (k = 2; k < prime2; k++)    //  changing point
            {
                if (prime2 % k == 0)
                {
                    flag++;
                    break;
                }
            }

            if (flag == 0)
            {
                printf("%d %d\n", i, prime2);
            }
        }
    }

    return 0;
}

很少有资源可以了解更多关于找出素数的信息：

如何列出所有性感素数对

how to list all pairs of sexy primes

c

primes