C で数値が素数かどうかを効率的に判断するにはどうすればよいですか?

C で素数を決定する方法

この質問では、C で指定された整数が素数であるかどうかを決定する方法について説明します。提供された元の C# ソリューションは次のとおりです。 :

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

これを C で実装する方法を理解するために、以下を詳しく見てみましょう。アルゴリズム:

1. 数値が負、0、または 1 であるかどうかを確認します。これらは素数ではありません。
2. 2 から数値の平方根まで反復します。
3. 反復ごとに、数値が現在の値で割り切れるかどうかを確認します。
4. 場合割り切れますが、その数は素数ではありません。
5. 約数が見つからないままループが完了した場合、その数は次のようになります。 prime.

このアルゴリズムを C に変換すると、次のようになります。

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

元の C# ソリューションとの違いは次のとおりです。

• bool は a ではありません。 C データ型なので、int を使用し、代わりに 0/1 を返します。
• stdbool.h はありません。
• 効率を上げるために、ループは数値の平方根まで反復されます。

以上がC で数値が素数かどうかを効率的に判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。