C言語 素数判定のコード

• nが素数の場合は、1を返し、そうでない場合は0を返す。
• intの範囲で考える
• 2秒以内に返す

参考にしたコード

int ft_is_prime(int nb)
{
    int i;

    i = 2;
    if (nb <= 1)
        return (0);

    while (i <= nb / i){
        if (nb % i == 0)
            return (0);
        i++;
    }
    return (1);
}

問題を見て考えたこと

実装

• 素数の定義の確認
  • ２が最小
  • intの最大値である2147483647は素数だが、何番目なのかは調べても出てこなかったため、計算量がわからない。→実際試してみて２秒以上かかるのかチェック。
• 基本
  • intの範囲限定なので、素数を順に比較していく
• 実装
  • 素数と一致すれば1を返す
  • 素数で割れると終了 0を返す
  • nが比較する素数より大きくなったら、終了 0を返す

テストケース

• intの中で最大の素数と最大-1の計算結果
• 最小の素数2の結果
• 0,1
• マイナスを与えたときの挙動
• 素数の一覧を出して軽く比較

実装コードを見て所感

• ループのコストを高く見積もり過ぎた。
  • 2147483647の素数判定でも2秒もかからない
• 単純に2147483647までの整数で割っていく方法で十分。
• もっとも単純な方法から、順に思考してくようにする。