最速の素数判定プログラム Python Java Kotlin C# C++

この記事で解決できる問題

競技プログラミングで素数判定をしたい
なるべく簡単で理解しやすいプログラムを書きたい
コピペで使えるコードが欲しい

この記事では競技プログラミングで使用できる、素数の判定プログラムを紹介します。
対応するプログラミング言語は、Python、Java、Kotlin、C#、C++です。

この記事のプログラムをコピペすれば、一瞬で高速な素数判定をすることができますよ！
実際に私もこの方法を使って問題を解いたことがありますが、処理速度の面で問題になったことはありません。

記事前半ではコピペで使えるプログラムを、後半ではプログラムの内容について解説します。
最後におまけもあるので、素数に関する小ネタが知りたい方は最後まで読んでみてくださいね！

素数判定プログラム

Python

import math

def is_prime(num):
    if num < 2:
        return False
    elif num == 2:
        return True
    elif num % 2 == 0:
        return False
    
    sqrtNum = math.floor(math.sqrt(num))
    for i in range(3, sqrtNum + 1, 2):
        if num % i == 0:
            return False
    
    return True

Java

public static boolean isPrime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = Math.sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

Kotlin

fun isPrime(num: Long): Boolean {
    return when {
        num < 2L -> false
        num == 2L -> true // 2は偶数だが素数
        num % 2L == 0L -> false // 偶数はあらかじめ除く
        else -> {
            val sqrtNum = sqrt(num.toDouble())
            for (i in 3..sqrtNum.toLong() step 2) {
                if (num % i == 0L) {
                    return false // 素数ではない
                }
            }

            return true // 素数である
        }
    }
}

C#

public static bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = Math.Sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

C++

#include <math.h> 

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

プログラム解説

実装しているアルゴリズムは主にこちらのサイトを参考にしています。

素数判定 | アルゴリズムとデータ構造 | Aizu Online Judge

ここから引用

まず、2 以外の偶数は素数ではないことを利用すれば計算量は半減、さらに x の半分まで調べれば十分と分かればさらに半減させることができます。しかしこれらの工夫を考慮しても O(x) のアルゴリズムに変わりはありません。
素数判定では、「合成数 x は p≤√x を満たす素因子 p をもつ」という性質を利用することができます。ここで、素数ではない数を合成数と言います。例えば、31 が素数かどうかの判定は、31 を 2 から 6 までの数で割ってみれば十分ということになります。もし 7 から30までの数で 31 を割り切れる数が存在するのであれば、すでに調べた 2 から 6 までの数に 31 を割り切れる数が必ず存在するので、6 を超えた数字を調べることは無駄になります。
これを利用すると、2 から x－1 までではなく、2 から √x までについて割り切れるかどうかを調べれば十分なので、O(√x) のアルゴリズムに改良することができます。これは、例えば x が 1,000,000 とすると√x = 1,000 となり、素朴なアルゴリズムの半減どころか 1,000 倍速くなります。

ゴイチ

ということは？・・

ここがポイント

素数判定では、「合成数 x は p≦√x を満たす素因子 p をもつ」という性質を利用することができるので、

「合成数 x は p ≦ √x を満たす素因子 p をもつ」＝「 x が合成数ならば、√x 以下の約数を持つ」となります。

そのためループの終了条件が √xになり、単純に x まで剰余演算をするのに比べると、ループ回数が減って処理速度が大幅に短縮されます。

実際に動かしてみる

では本当に素数判定が出来るのか、具体例をいくつか紹介します。

fun main(args: Array<String>) {
    println("2 is ${isPrime(2)}")
    println("3 is ${isPrime(3)}")
    println("13 is ${isPrime(13)}")
    println("1023 is ${isPrime(1023)}")
    println("3571 is ${isPrime(3571)}")
    println("2147483647 is ${isPrime(2147483647)}") // 10桁のメルセンヌ素数
    println("200560490131 is ${isPrime(200560490131)}") // 12桁のユークリッド素数
    println("92709568269121 is ${isPrime(92709568269121)}") // 14桁の素数
    println("9007199254740997 is ${isPrime(9007199254740997)}") // 16桁の素数
    println("1565912117761 is ${isPrime(1565912117761)}") // 13桁の合成数(1162193×1347377)
    println("8635844967113809 is ${isPrime(8635844967113809)}") // 16桁の合成数(89652331×96325939)
    // https://tools.m-bsys.com/calculators/prime_number.php
}

出力結果

2 is true
3 is true
13 is true
1023 is false
3571 is true
2147483647 is true
200560490131 is true
92709568269121 is true
9007199254740997 is true
1565912117761 is false
8635844967113809 is false

出力結果は期待通りの結果になっています。処理速度も問題ないようです。

まとめ

素数の判定をするには以下を順に実施します。

素数判定

2未満の数を除去する（素数ではない）
2は偶数だが例外的に素数なので除去する（素数である）
3以上の数で偶数のものを除去する（素数ではない）
3〜√nまでの数で割り切れるものを除去する（素数ではない）
割り切れるものがなければ素数である（素数である）

以上の手順をプログラムで表現すれば、素数判定をすることが出来ます。
厳密に言えば、もっと速いプログラムは存在しますが、競技プログラミングの問題を解くのに必要な速度は出せるレベルにはなっています。

ゴイチ

このプログラムで速度が足りない場合は、素数判定自体が問題になっているか、問題が悪いと思います（笑

競技プログラミングの問題で素数判定が出てきたら、是非この記事を思い出してコピペしてみて下さいね！

おまけ

数学用語の解説

もっと詳しく

素数とは？　→　1と自分自身以外の数で割り切れない自然数のこと
合成数とは？→　素数以外の数のこと

その他の素数判定アルゴリズム

素数判定アルゴリズムは大きく分けて２種類が存在するようです。

決定的素数判定法
確率的素数判定法

決定的判定法とは、確実に誤りが出ない方法で素数判定を行うというもの。
確率的判定法とは、たまに誤りが出るかもしれないけど判定速度が劇的に速くなる方法。

決定的素数判定法の代表格は、「AKS素数判定法」
確率的素数判定法の代表格は、「ミラーラビン素数判定法(Miller-Rabin primality test)」

より速い実装が必要な方はこちらのアルゴリズムも検討してみてください。

（注）この記事はQiitaに投稿した過去の記事を再構成したものです

この記事は役に立ちましたか？

フィードバック頂けると励みになります！