[Boot camp for Beginners] C - Next Prime [Rust]

2023-11-02

概要

素数を求める...なんだっけ、アイヤストラの櫛(くし)みたいなやつ...
- エラトステネスの篩(ふるい)だった
- うろ覚えがすぎる
エラトステネスの篩で、ある数以下の最大の素数は求められる
- x 以上の素数をこれで求めるには？
- xの2倍以下の素数を求めてみて、x以上の素数が出てきたら止めれば良さそう
エラトステネスの篩を実装したことない...
- 素数のリストはいらないし、篩用の配列と閾値と一つ前の素数を引数にして再帰すれば良さそう
毎回実行時に計算すると MLE になる
- MLEになったの初めてだ...どうすればいいか
- コンパイル時計算とか必要...?
- 色々いらんことしすぎて混乱してきた

解説など見て仕切り直し

まずは実直にエラトステネスの篩を実装してみる
- アルゴリズム通りにループで普通に書く
x が 10^5 までの範囲なので、10^6 までの素数を求める
その中で x より大きいものを find する
これでいけた
- 初見でエラトステネスの篩を書くの無理では...？
  - 最終的に20stepぐらいで書けるが試行錯誤必要
- まずエラトステネスの篩を思いつけないと解けない

[Boot camp for Beginners] C - Next Prime [Rust]

2023-11-02