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のことは忘れて、ある数字を与えて、それが素数かどうか判断してもらうとします。 あなたはどのようにそれを行うのですか？ その手順を明確に書き出してください。 では コードに変換することを心配する。

アルゴリズムが決まれば、プログラムの書き方を考えるのも、他の人に手伝ってもらうのも、ずっと楽になります。

を編集してください。 投稿されたC#のコードです。

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

これは ほぼ はそのまま有効な C 言語です。 bool 型はありませんし true または false というように、少し修正する必要があります (編集: Kristopher Johnson は、C99 が stdbool.h ヘッダを追加したことを正しく指摘しています)。 C99環境にアクセスできない人もいるので（でも使うべきです！）、その非常に小さな変更を行いましょう。

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

これは、あなたが望むことを行う完全に有効なCプログラムです。 あまり労力をかけずに、少し改良することができます。 まず、以下の点に注意してください。 i は常に number というチェックが入るので i != number は常に成功するため、これを取り除くことができます。

までの約数を実際に試す必要はありません。 number - 1 までの約数を試す必要はなく、sqrt(number)に到達した時点でチェックを止めることができます。 というのも sqrt は浮動小数点演算であり、微妙な点が山ほどあるため、ここでは実際に sqrt(number) . そのかわり i*i <= number :

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

最後にもう一つ、あなたのオリジナルのアルゴリズムには小さなバグがありました。 もし number が負、0、または 1 の場合、この関数はその数が素数であると主張します。 あなたはそれを適切に処理したいと思うでしょうし、そのために number を符号なしとしたいと思うかもしれません。

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;
}

これは数字が素数かどうかをチェックする最速の方法ではないことは確かですが、動作しますし、とても簡単です。 私たちはあなたのコードをほとんど変更する必要がありませんでした。