アルゴリズムプログラミング書き方

アルゴリズム ② 1+2+・・+nで記載（根性）またはsum. 今回は、素数を数えるためのいろいろなアルゴリズムや高速化について書きます。（言語はJavaを使います）プログラミング初心者の方、アルゴリズムについて勉強したい方、素数が大好きな皆さんの参考になればと思います。

プログラムの書き方. これまでは、ただ単にプログラムの書き方を見てきた。HTML&CSS講座、JavaScript講座は、それぞれでやりたいことがある前提で、それをプログラムで表現することを解説してきた。今更新中のjQuery講座もそうだ。で、ここまでや分岐処理：「ある条件」に応じて処理（命令）を2通り以上に分けて実施する 3. 7．疑似言語疑似言語とは擬似言語（ぎじげんご）は、擬似的なプログラミング言語のことで、一般的に使われる記述法を交えることで、アルゴリズムの理解などを助けるために使われる。この擬似言語は、基本情報技術者試験独自のものなので、試験問題に仕様書が添付されている。必要な勉強や技術の最新動向、本当に使えるIT資格、学習に役立つ国からの奨励金などの情報を無料でお届け All rights reserved. ITエンジニア向け総合求人・学習サービス「paiza」の開発者が、プログラミングやITエンジニアの転職などについて書いています。人間、どうしても素数を数えて落ち着きたいときってあると思います。順に数えてくと、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31……自分で数えるのは限界がありますよね。そんなときはプログラムに数えてもらいましょう。今回は、素数を数えるためのいろいろなアルゴリズムや高速化について書きます。（言語はJavaを使います）プログラミング初心者の方、アルゴリズムについて勉強したい方、素数が大好きな皆さんの参考になればと思います。素数とは、1と自分自身の数以外の自然数では割り切れない孤独な数字です。(ってプッチ神父が言ってました)たとえば、7は1と7以外の自然数では割り切れないので素数です。8は2や4で割り切れるので素数ではありません。※1は諸説ありますが、今回はひとまず素数ではないものとします。皆さんは、素数を数えて落ち着きたいときはどうやって数えていますか？「2は素数、3は素数、4は2で割り切れるから素数ではない、5は素数、6は2でも3でも割り切れるから素数ではない……」と数字ひとつひとつに対して、「素数か否か」を確認しながら数えますよね？（ある程度までは暗記していたとしても、それを越えたら確認が必要になってきますよね）そんなときは「ある自然数が素数かどうか」を判定してくれる素数判定プログラムを作っておくと、楽になります。素数判定プログラムを作るには、まず以下のようなisPrimeメソッドを作っておきましょう。大きな値でも対応できる素数判定を作るのは大変ですから、徐々に改善しつつやっていきましょう。まずは、10以下の自然数nの素数判定プログラムを作成します。10以下の素数はほんの少しですから、そのまま条件を書き出すだけでいけちゃいますね。こんな感じです。↑このままいじれますので、nの値を変更してテストしてみてください。ちゃんと3や7が素数と判定されて、1や8は素数でないと判定されるので、大丈夫そうですね。次に、100以下の自然数nの素数判定プログラムです。100以下もまあそんなに多くはないですから、そのまま条件を書いてみました。10以下のときと同じように、nの値をいろいろ変えて試してみてくださいね。ブログパーツとして使っているオンライン実行環境サービス「1,000以下になるとどうでしょうか、さすがに全部書き出すのは面倒すぎますね。「素数は1と自分自身の数以外の自然数では割り切れない孤独な数字」なんですから、2以上であること、もしくはn-1以下の整数で割り切れないことを確認すれば判定できそうですね。n = 1の場合の処理を忘れずに入れておきますnの値を1,000以下の大きな数値にして試してみましょう。991は素数で、989は素数ではないようです。前述のコードで、とりあえず大きな数値でも判定できるようになったっぽいですよね。nを大きくしながら実行していくと、ひとまず9,999,991は素数、9,999,992は素数ではないと判定できます。ただ、これぐらいの大きさの数になってくると、というわけでここからは、大きな数値でも素早く判定できるような高速化を考えていきます。プログラムを高速化するにはどうすべきか？いろいろな手法がありますが、単純にループの回数が減れば、そのぶん処理も早く終えられます。そもそも偶数（＝2の倍数）はすべて素数じゃないですから、偶数の場合はループでチェックするのをやめてみましょう。これだけでも、ループ回数がおよそ半分になります。このコードを実行してみると、さきほど0.50秒程度かかっていた数値での実行時間が0.38秒となりました。およそ0.12秒の高速化ですね。偶数の次は、3の倍数も外してみましょうか。ちょっとややこしいですが、こんな感じです。2の倍数、もしくは3の倍数が出現するパターンは6ごとに周期的に繰り返されますから、周期の中で2の倍数でも3の倍数でもない数についてだけ、素数チェックをするようにしました。これによって実行時間が0.30秒となり、偶数だけ外していたときよりも、さらに0.08秒高速化できました。さらにに5の倍数が入るとどうなるか？2の倍数か3の倍数か5の倍数が出現するパターンは30ごとに周期的に繰り返しますから、周期の中でいずれの倍数でもないものだけチェックに回すようにしました。実行時間は、0.29秒でした。0.01秒だけ早くなりましたが、倍数チェックだけ増やしても、そこまで大きくは改善されませんね。さらに範囲を広げて、1,000,000,000（10億）以下の自然数nの素数判定プログラムを作成します。さっきのプログラムで999,999,937を判定すると、実行時間は1.01秒でした。さきほどより0.72秒遅くなっていますね。2,3,5の倍数を省略してきたので、7の倍数も追加したい気持ちになりますが、その場合周期が210(= 2 x 3 x 5 x 7)となって210通りの場合分けを考えなければならず、かえって非効率ですね。もっとよいアプローチが必要です。ここで、素数ではない自然数の約数について考えてみましょう。例えば、81の約数は 1, 3, 9, 27, 81ですよね。約数は、両端から順にペアにして掛け算すると 1 x 81, 3 x 27, 9 x 9 となって、いずれも積は81です。81を3で割ると対応する27になるってことは、81は27でも割り切れるってことですね。このように、素数判定するなら約数を並べて前半の半分（81の場合は9）までで割り切れるかどうかを調べればよいわけです。この半分の数値は、sqrt(81) にあたる数値です。つまり、プログラム的にはsqrt(n)以下の数についてだけ割り切れるかどうかを調べればOKなんです。これを踏まえてコードを書き直すと…数学ライブラリの平方根の計算は浮動小数点誤差が気になるため、1回分余裕をもってループを回すようにしています。実行すると0.19秒で、1.01秒と比べると0.82秒も高速化できました。さらにもう少しコードを整理しましょう。i <= sqrt(n) という条件は、i x i <= n に置き換えられます。こちらの方が浮動小数点が出てこなくて、すっきり高速に計算できるはず。実行時間を確認すると0.19秒……先ほどと変わっていませんが、0.01秒未満の範囲で若干高速化されてるはずです。少なくとも10億以下の自然数に対してはそんなに悪くない実行時間で素数判定できるようになりました。では、いよいよ素数を数えて落ち着いていきましょう。以下のようなprimesListメソッドを作ります。素数をたくさん表示させようとすると標準出力に時間がかかるので、ひとまず1,000以上の大きな素数は表示せずに、数えた素数の個数と1,000未満の素数の一覧だけが表示されるようにしています。まずは10以下の素数を数えます。素数判定のときと同じ要領で、全部書いてみました。10以下の素数4つを数えて落ち着きました。次に、1,000以下の素数を数えます。さきほど作った素数判定を使ってやってみましょう。1,000以下の168個の素数を0.20秒で数えることができました。いい感じですね。次に、10,000,000以下の素数を数えてみたいのですが、先ほどのコードでそのまま実行すると、ここから一気に1万倍ぐらい高速化するにはどうすべきか？素数判定のときに、2と3と5の倍数については判定しないようにしましたよね。自身を除いて何らかの倍数である数値は、素数ではありません。「素数を見つけたら都度その倍数をすべて素数候補から除外することで、素数を絞り込んで見つけやすくする」という処理をすると、小さな素数から順にどんどん見つけていくことができます。このようなアルゴリズムを「エラトステネスの篩（ふるい）」といいます。（コードは以下のようになります。ちょっと長いですが、「sieve[i]がtrueなら、iは素数である」というコードです。sieveの要素は最初はすべてtrueであり、そこから素数でない0, 1を除いて、素数である2の2倍以上の倍数：4, 6, 8, 10…...と順に候補から除外します。2の倍数の除外が終わったら、次は3の2倍以上の倍数6, 9, 12, ...と順に候補から除外します。このプログラムを実行してみると、1.03秒で実行が終了し、10,000,000以下の素数が664,579個あるとわかりました。さっきはタイムアウトしていたプログラムが、エラストテネスの篩のおかげで非常に高速に動作するようになりましたね！しかし、素数の範囲をさらに拡大してn = 100,000,000にしてみると、タイムアウトしてしまいました。これをさらに高速化するには、どうすればいいと思いますか？素数判定のときは、sqrt(n) までの自然数で割り切れるかどうかを調べれば、nが素数かどうか判定できましたよね。この性質をエラトステネスの篩でも活用してみましょう。ふるう区間を sqrt(n) 個に分割して、それぞれの区間に個別にふるいを適用します。まず、0から sqrt(n)-1 までの範囲の素数のリストをエラトステネスの篩で求めます。この素数のリストがあれば、残りの sqrt(n)-1 個のそれぞれの区間をふるうことができます。このように、エラトステネスの篩を特定の区間に適用する操作を「区間篩」といいます。コードにするとこんな感じ。↓この辺はインデックスの調整がやや込み入っていますが「すでに見つかっている素数pの倍数をうまく探している」と理解しておいてください。pの倍数を探すので、pで割った余りが重要な意味を持ちます。このコードを実行すると実行時間1.79秒で、一億以下の素数5,761,455個すべてを数えることができました。ようやく落ち着きましたね。というわけで、一億以下の素数に適用できるアルゴリズムを紹介しました。さらに大きな素数を数えたい人は、フェルマーテスト（また、今回のはエラトステネスの篩と区間篩を利用しました。ふるいを使った素数判定法はほかにもありますので、興味のある人は試してみてください。数学的な理屈よりも、計算機を回して世界で一番ビッグな素数を探したいという人は、メルセンヌ素数の概要をつかんで、GIMPS (Great Internet Mersenne Prime Search)プロジェクトに参加するのがよいかと思います。（ビットコインのマイニングよりもロマンがあるかもしれません）「素数を自分で数えるのは苦手だけど眺めるのは好き」という人は、OEIS (The On-Line Encyclopedia of Integer Sequences)で好みの素数に関連する数列を探してみてください。「そこまで素数に興味がない」という人（よくここまで読みましたね）も、GNUの素因数分解コマンドの factor/gfactor だけでも知っておくと、素数に関して何かあったときに役立つと思います。また、動画でプログラミングが学べる「途中で出てきた画像の漫画はそして、スキルチェックに挑戦した人は、その結果によって

まず、はじめに一番シンプルな書き方から紹介します。単純にif文のみある場合です。

松井稼頭央なんj メジャー, 荒野行動ガチャ当たりやすい時間, Be The One MP3, このままいくと英語, 横須賀線成田空港時刻表, Pubgモバイルゾンビモードやり方, プロ野球新人王 2018, 和泉屋旅館京都, 結婚顔で選んで後悔男, 弓長さ測り方, 橋本環奈片寄涼太映画, ヤクルト杉浦亨現在, Ssw Fallout 4, 鎧の孤島教え技場所, ベートーベン弦楽四重奏有名, 大宮軽井沢新幹線グリーン料金, 新幹線立ち席過ごし方, スーパー北斗時刻表新函館北斗, 日大アメフト宮川現在, クロノトリガーサントラ MP3, 嵐にしやがれゲスト一覧, ハンドウォーマー棒針編み図, 京都牝馬ステークス 2020 過去, 暗い暗い暗い Don't Cry Udk, クロマニヨンズエイトビート名曲, 膵炎を繰り返した有名人, トーマススライム YouTube, 大学行く意味 2ch, コナンアイリッシュ Pixiv, 下松駅みどりの窓口, ポケモンサンムーンユーチューブ, ファクタリング即日少額, 株式会社スマイルマスク口コミ, Amazarashi ロングホープフィリア, つるの剛士バイク Cm, 国中で英語, テイルズオブクレストリア攻略, PS4 リモートプレイ Steam, ダイオード該非判定, ミッドサマー配信 Amazon, ファフナー Vバトルかずき, 慶應応援指導部ニュース, ゼクシィ雑誌広告, PUBGモバイル敵の場所, ポケモン BW2 リオル色違い, エイダンクイン病気, 今井美樹 Pride Mp3, コクヨファイルフラットファイル A4 10冊入, 電車トイレ流れない, トイプラネット子供服買取, タイガーカワシマちびメイト, マツコ会議ゆうたろう現在, グラデーション英語使い方, ゼクシィ縁結び強制退会, アイリスヘルスケアマスク 7枚, Carbon8 M45 マルイ互換, びわ湖毎日マラソン 2020 交通規制, 空気銃狩猟キジ,