2

b = a + 2、c = b + 4、 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

ご覧のとおり、私のソリューション (上記の最初の出力セット) には、正しいソリューション (上記の 2 番目の出力セット) にすべてのプライム シーケンスが含まれており、いくつかの追加のソリューションが含まれています。私の解には、a、b、c、d、e、f の間に冗長な素数があるとアドバイスされています。これが、適切な解に含まれる解が少ない理由です。出力の一部の行が冗長である理由を誰かが説明できますか (質問の主な条件に適合しているようです)? また、ソリューションから冗長なセットを削除するにはどうすればよいですか?

4

3 に答える 3

7

任意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 に答える