素数判定法

素数判定とは

与えられた整数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;
}

多分こんな感じ。確認もしてないです。実際に使ったりしたらその時に書き直したやつをコピペします。