Blue_S https://blog.hatena.ne.jp/Blue_S/ 競プロ解法まとめ https://blue-s.hatenadiary.com/ 素数判定とは 与えられた整数nが素数かそうでないかを判定するアルゴリズムである。 普通に考えると、2 ~ n-1 でnが割り切れないかを確認すれば良い。しかし、 n = abとすると、min(a, b)は√nを超えない。これより2 ~ √nの間でのみ割り切れないかを考えると十分であり、これはO(√n)の計算量で実行できる。 実装 fn is_prime(n: usize) -> bool { for i in 2..(n + 1) { if i.pow(2) > n { break; } if n % i == 0 { return false; } } return true; } 多分こん… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblue-s.hatenadiary.com%2Fentry%2F2023%2F11%2F01%2F044612" title="素数判定法 - 競プロ解法まとめ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-11-01 04:46:12 rich https://blue-s.hatenadiary.com/entry/2023/11/01/044612 1.0 100%