2

我正在尝试用 C 语言编写一个程序，该程序以 b = a + 2，c = b + 4 的方式查找所有连续 5 位素数（a、b、c、d、e、f）的序列， d = c + 6、e = d + 8 和 f = e + 10。

我的解决方案如下：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>


bool IsPrime(int x){

    for (int i = 2; i < x; i++){
        if (x % i == 0 && x != i) return false;
    }
    return true;
}           


int main(void){

    int a,b,c,d,e,f;


    for (int i = 10000; i < 99999; i++){
        if (IsPrime(i) == true && IsPrime(i + 2) == true && IsPrime(i + 6) == true && IsPrime(i + 12) == true && IsPrime(i + 20) == true && IsPrime(i + 30)){
            a = i;
            b = i + 2;
            c = i + 6;
            d = i + 12;
            e = i + 20;
            f = i + 30;
            printf("%i %i %i %i %i %i \n", a, b, c, d, e, f);
            a, b, c, d, e, f = 0;
        }
    }



// end
}

给出以下输出：

13901 13903 13907 13913 13921 13931

21557 21559 21563 21569 21577 21587

26681 26683 26687 26693 26701 26711

28277 28279 28283 28289 28297 28307

31247 31249 31253 31259 31267 31277

33617 33619 33623 33629 33637 33647

55661 55663 55667 55673 55681 55691

68897 68899 68903 68909 68917 68927

97367 97369 97373 97379 97387 97397

但是，正确的解决方案显然是：

13901   13903   13907   13913   13921   13931

21557   21559   21563   21569   21577   21587

28277   28279   28283   28289   28297   28307

55661   55663   55667   55673   55681   55691

68897   68899   68903   68909   68917   68927

如您所见，我的解决方案（上面的第一个输出集）包含正确解决方案（上面的第二个输出集）中的所有素数序列，以及一些额外的解决方案。我被告知我的解决方案在 a、b、c、d、e 和 f 之间有多余的素数，这就是为什么正确的解决方案包含更少的解决方案。有人可以解释为什么我的输出中的某些行是多余的（它们似乎符合问题的主要条件）？另外，如何从我的解决方案中消除冗余集？

4

3 回答 3

7

对于 any i，您正在检查以下内容的素数：

i
i + 2
i + 6
i + 12
i + 20
i + 30

如果所有这些都是素数，它仍然不满足谓词，除非您还确定这些是连续的素数。因此，您需要检查数字i + 4、i + 8等（向上到i + 28）是否不是素数。（您不需要检查，因为如果并且两者都是素数，i + an_odd_number它们永远不会是素数。）ii + 2

于 2013-04-29T07:04:20.953 回答
0 
//Fixed

bool IsPrime(int x){
    //some changes to make the code run faster.
    if (x < 2) return false;
    for (int i = 2; i*i < x; ++i)
    {
        if (x % i == 0) return false;
    }
    return true;
}           


int main(void){

    int a,b,c,d,e,f;


    for (int i = 10001; i < 99999; i+=2){
        //continue for all the wrong cases.
        if (!IsPrime(i)) continue;
        if (!IsPrime(i+2)) continue;
        if (!IsPrime(i+6)) continue;
        if (!IsPrime(i+12)) continue;
        if (!IsPrime(i+20)) continue;
        if (!IsPrime(i+30)) continue;

        //Those checks if you need to validate no primes in the middle.
        if (IsPrime(i+4)) continue;
        if (IsPrime(i+8)) continue;
        if (IsPrime(i+10)) continue;
        if (IsPrime(i+14)) continue;
        if (IsPrime(i+16)) continue;
        if (IsPrime(i+18)) continue;
        if (IsPrime(i+22)) continue;
        if (IsPrime(i+24)) continue;
        if (IsPrime(i+26)) continue;
        if (IsPrime(i+28)) continue;

        //If we got here, all is good.
        a = i;
        b = i + 2;
        c = i + 6;
        d = i + 12;
        e = i + 20;
        f = i + 30;
        printf("%i %i %i %i %i %i \n", a, b, c, d, e, f);
    }

// end
}

一种更快的方法是将检查“素数”的最后 15 个奇数保存在数组（或任何其他方式）中，然后仅检查序列是否正确。因为在当前方法中，您可以检查一个数字是否为素数最多 15 次。

于 2013-04-29T07:41:12.717 回答
0

您没有注意素数是连续的要求，并且您的代码比需要的要慢得多。保留最后 6 个素数的队列，将每个素数插入队列末尾并丢弃第一个……这可以通过循环数组轻松完成。每次插入素数时，请检查差异条件是否适用……如果适用，则有解决方案。

对于您的 IsPrime 例程，您只需要检查 x 的平方根，并且您不需要检查 i != x 因为它总是更少。

这是一个有效的解决方案：

#include <stdio.h>
#include <stdbool.h>

static inline int next(int i)
{
    return (i + 1) % 6;
}

static void check(int* p, int x)
{
    for (int i = 0; i < 5; i++, x = next(x))
        if (p[next(x)] - p[x] != (i+1) * 2)
            return;

    for (int i = 0; i < 6; i++)
        printf("%d%c", p[x = next(x)], i == 5? '\n' : ' ');
}

static bool isPrime(int n)
{
    for (int i = 3; i*i < n; i += 2)
        if ((n % i) == 0)
            return false;
    return true;
}

int main(int argc, char** argv)
{
    int cp[6] = { 0 };
    int x = 0;

    for (int i = 10001; i <= 99999; i += 2)
        if (isPrime(i))
        {
            cp[x] = i;
            check(cp, x = next(x));
        }

    return 0;
}

一个更快的解决方案将使用预先计算的素数表......使用

static int primes[316]; // sqrt(99999)
static int nprimes;

static bool isPrime(int n)
{
    for (int i = 0; i < nprimes; i++)
        if ((n % primes[i]) == 0)
            return false;
    return true;
}

并添加

for (int n = 3; nprimes < 316; n += 2)
    if (isPrime(n))
        primes[nprimes++] = n;

在主循环之前。

对于具有非常大素数的一般解决方案，您可以使用Erastothenes 分段筛产生前 N 个素数。

于 2013-04-29T07:56:05.470 回答