3 
int prime(unsigned long long n){
    unsigned val=1, divisor=7;
    if(n==2 || n==3) return 1; //n=2, n=3 (special cases).
    if(n<2 || !(n%2 && n%3)) return 0; //if(n<2 || n%2==0 || n%3==0) return 0;
    for(; divisor<=n/divisor; val++, divisor=6*val+1) //all primes take the form 6*k(+ or -)1, k[1, n).
        if(!(n%divisor && n%(divisor-2))) return 0; //if(n%divisor==0 || n%(divisor-2)==0) return 0;
    return 1;
}

上記のコードは、友人が素数を取得するために作成したものです。ある種のふるい分けを使用しているようですが、正確にどのように機能するかはわかりません。以下のコードは、それほど素晴らしいバージョンではありません。私は自分のループに使用sqrtしますが、彼が何か他のことをしているのを見た (おそらく関連するふるい) ので、気にしませんでした。

int prime( unsigned long long n ){
    unsigned i=5;
    if(n < 4 && n > 0)
        return 1;
    if(n<=0 || !(n%2 || n%3))
        return 0;
    for(;i<n; i+=2)
        if(!(n%i)) return 0;
    return 1;
}

私の質問は、彼は正確に何をしているのですか?

4

5 に答える 5

5

あなたの友人のコードは、N > 3 の場合、M = 1、2、... の場合、すべての素数が (6×M±1) の形式をとるという事実を利用しています (したがって、M = 1 の場合、素数の候補は N = 5 と N = 7 で、どちらも素数です)。また、すべての素数のペアは 5 と 7 のようなものです。これは 3 つの奇数のうち 2 つだけをチェックしますが、ソリューションは 3 つの奇数のうち 3 つをチェックします。

あなたの友人のコードは、平方根に似た何かを達成するために除算を使用しています。つまり、条件divisor <= n / divisorはほぼ同等ですが、より遅く、オーバーフローから安全divisor * divisor <= nです。unsigned long long max = sqrt(n);ループの外で使用する方が良いかもしれません。これにより、より多くの可能な値を検索する提案されたソリューションと比較して、チェックの量が大幅に削減されます。平方根チェックは、N が複合の場合、係数 F と G の特定のペア (F×G = N など) に対して、それらの 1 つが N の平方根以下であり、もう一方は、N の平方根以上になります。

Michael Burrが指摘しているように、友人の素数関数は 25 (5×5) と 35 (5×7) を素数として識別し、1000 未満の 177 個の数を素数として生成しますが、その範囲には 168 個の素数しかないと私は信じています。その他の誤認複合体は、121 (11×11)、143 (13×11)、289 (17×17)、323 (17×19)、841 (29×29)、899 (29×31) です。

テストコード:

#include <stdio.h>

int main(void)
{
    unsigned long long c;

    if (prime(2ULL))
        printf("2\n");
    if (prime(3ULL))
        printf("3\n");
    for (c = 5; c < 1000; c += 2)
        if (prime(c))
            printf("%llu\n", c);
    return 0;
}

固定コード。

元のコードの問題点は、チェックdivisorする 2 つの数値のうち小さい方ではなく大きい方に設定されているため、すぐにチェックを停止してしまうことです。 

static int prime(unsigned long long n)
{
    unsigned long long val = 1;
    unsigned long long divisor = 5;

    if (n == 2 || n == 3)
        return 1;
    if (n < 2 || n%2 == 0 || n%3 == 0)
        return 0;
    for ( ; divisor<=n/divisor; val++, divisor=6*val-1)
    {
        if (n%divisor == 0 || n%(divisor+2) == 0)
            return 0;
    }
    return 1;
}

末尾のコメントで省略形の否定条件を説明する必要がないため、リビジョンの方が理解しやすいことに注意してください。ループの本体の+2代わりにも注意してください。-2

于 2012-04-23T04:48:59.433 に答える
2

彼は基底 6k+1/6k-1 をチェックしています。これは、すべての素数がその形式で表現できるためです (また、すべての整数は 6k+n の形式で表現でき、ここで -1 <= n <= 4)。そうです、それはふるい分けの一種です..しかし厳密な意味ではありません.

詳細: http://en.wikipedia.org/wiki/Primality_test

于 2012-04-23T04:44:19.470 に答える
1

6k+-1 の部分がわかりにくい場合は、ほとんどの形式の因数分解を実行でき6k+n、一部は明らかに合成され、一部はテストする必要があることに注意してください。

数字を考えてみましょう:
6k + 0 -> 合成
6k + 1 -> 明らかに合成ではない
6k + 2 -> 2(3k+1) --> 合成
6k + 3 -> 3(2k+1) --> 合成
6k + 4 -> 2(3k+2) --> コンポジット
6k + 5 -> 明らかにコンポジットではない

私は前にこの小さなトリックを見たことがないので、それはきちんとしていますが、多くの小さな素数を見つけるにはエラトステネスのふるいがより効率的であり、より大きな素数はより速く、よりインテリジェントなテストの恩恵を受けるため、有用性は限られています.

于 2012-04-23T05:05:52.150 に答える