素数判定

ある整数が素数かどうか判定したいことは良くあると思います。それをプログラムで表すにはどうすればいいか ? というのは、初心の人にはなかなか分からないと思います。

そもそも素数とは、1 と自分自身しか約数を持たない 2 以上の整数のことを指します(負の数は考えないのが一般的です)。ということは、2 から順に 2 , 3 , 5 , 7 , 11 , …となります。これをプログラムでどう実現したら良いでしょう ?

2 以上の整数 n が与えられたとき、n を順々に小さい方から素数で割ってみて、余りが出なければ(= 割り切れれば)、それは素数ではありません。しかし、このような判定を、n より小さい素数全てで行う必要はありません。もし、 より大きい数で割りきれたなら、それは必ず より小さい数でも割り切れるはずです。従って、判定に用いる素数としては なるものだけで十分なはずです。

まぁ説明はこのくらいにして、実際のソースを見ていただきましょう。

public class IsPrime {
    private IsPrime() {}

    public static boolean isPrime(int n) {
        boolean prime = true;
        int p = 2;

        while(p * p <= n) {
            if(n % p == 0) {
                prime = false;
                break;
            }

            if(p == 2) {
                p = 3;
            } else {
                p += 2;
            }
        }

        return prime;
    }
}

p として 2 以降は となる奇数を取っていますが、これは、素数をいくつ記憶しておけばいいか分からないので、計算を簡略化するためにこう書いています。で、p で割り切れる(= 余りが 0)ときは素数でないことを boolean 型変数を false にすることで示しています。このソースは Java で書きましたが、他の言語でも似たような書き方をすると同じことができます。ちなみにこのソースは他のプログラム内で

boolean flg = IsPrime.isPrime(n);

のように使います。