C LANGUAGE TECHNOLOGY

【C言語】エラトステネスの篩(ふるい)で素数の判定【サンダラムの篩,アトキンの篩】

悩んでいる人

C言語で素数の判定方法を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

エラトステネスの篩(ふるい)

エラトステネスの篩(ふるい)は,古代ギリシアの科学者のエラトステネスにより提案された素数を判定するアルゴリズムです.

1からNまでの自然数の中で素数を判定する時によく利用されます.

エラトステネスの篩のコードは以下になります.

実行結果は以下になります.

1から100までの素数を正しく判定できました.

サンダラムの篩

サンダラムの篩は,1934年にサンダラムにより提案された素数を判定するアルゴリズムです.

エラトステネスの篩は自然数を篩にかけるのに対して,サンダラムの篩は奇数を篩にかけることが特徴です.

これにより,サンダラムの篩は約2倍の高速化が期待できます.

サンダラムの篩のコードは以下になります.

実行結果は以下になります.同様です.

アトキンの篩

アトキンの篩は,2003年にアトキンにより提案された素数を判定するアルゴリズムです.

アトキンの篩の特徴は,自然数を60で割った余りを返す処理があることです.

この処理より,アトキンの篩は他の篩より高速化することが可能になります.

アトキンの篩のコードは以下になります.

実行結果は以下になります.同様です.

アトキンの篩の実装で利用するsqrt関数を知りたいあなたはこちらからどうぞ.

C言語 sqrt/sqrtf/sqrtl関数
【C言語】平方根を計算するsqrt/sqrtf/sqrtl関数の使い方と自作関数

こういった悩みにお答えします. こういった私から学べます. 目次1 平方根を計算するsqrt/sqrtf/sqrtl関数2 sqrt/sqrtf/sqrtl関数の使い方3 sqrt/sqrtf/sqr ...

続きを見る

まとめ

C言語のエラトステネスの篩(ふるい)で素数の判定方法を紹介しました.

また,エラトステネスの篩を改良したサンダラムの篩とアトキンの篩も解説しました.

素数の判定方法の高速化を知りたいあなたは以下の記事を読みましょう!

素因数分解アルゴリズムを知りたいあなたはこちらからどうぞ.

C言語 素因数分解
【C言語】素因数分解アルゴリズム【試し割り法,SPF法】

こういった悩みにお答えします. こういった私から学べます. 本記事は,素数の判定方法を理解していることを前提とします. 目次1 素因数分解2 試し割り法3 Smallest Prime Factor( ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , ,