現状で自己最速の素数チェッカーを作った

去るABC149のC問題で、素数に関する問題が出た。

過去問を解いてただけだけど、久々に素数判定の関数を書いた。

一応そこそこの素数チェッカーは書けたけど、改めて自分にどれくらいの素数チェッカーが書けるのか挑戦してみようと思う。

言語はPython3

ソース

# /usr/bin/env python3
# -*- coding:utf8 -*-

import math

# 自己ベスト更新を狙う素数チェッカー
def is_prime(num):
    if num % 2 == 0:
        # 素数の中で唯一2だけが偶数
        # それ以外の偶数は問答無用で合成数
        return True if num == 2 else False
    # sqrt(num)以下の数字だけ対象にすればOK
    N = int(math.sqrt(num))
    # 偶数は評価済みなので探索範囲を半分にする
    N = N >> 1
    for i in range(N):
        # 1は素数でないことに注意
        n = (i<<1)+3
        if num % n != 0:
            continue
        # 割り切れてしまった => nはnumの約数
        return False
    # 奇数を全部見たけど割り切れなかった => 素数
    return True

# コンテスト(過去問)で実装した素数チェッカー
def is_prime0(num):
    for i in range(2, int(math.sqrt(num))):
        if num % i == 0:
            return False
    return True

# 何も考えずに実装したオーソドックスな素数チェッカー
def is_prime1(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

if __name__ == '__main__':
    N = int(10e5)
    from datetime import datetime
    print("START: {}".format(datetime.now().strftime('%Y/%m%d %H:%M:%S')))
    print()

    # オーソドックスな素数チェッカー
    start = datetime.now()
    for i in range(2,N):
        is_prime1(i)
    end = datetime.now()
    prime1 = (end - start).total_seconds()

    # 実際に使った素数チェッカー
    # ループ上限値を調整した素数チェッカー
    start = datetime.now()
    for i in range(2,N):
        is_prime0(i)
    end = datetime.now()
    prime0 = (end - start).total_seconds()

    # サンダラムの篩を知って改良した
    # 素数チェッカー
    start = datetime.now()
    for i in range(2,N):
        is_prime(i)
    end = datetime.now()
    prime = (end - start).total_seconds()

    print("prime1 : {}".format(prime1))
    print("prime0 : {}".format(prime0))
    print("prime : {}".format(prime))
    print("is_prime1 / is_prime1 : {}".format(prime1/prime1))
    print("is_prime1 / is_prime0 : {}".format(prime1/prime0))
    print("is_prime1 / is_prime  : {}".format(prime1/prime))

    print()
    print("END  : {}".format(datetime.now().strftime('%Y/%m%d %H:%M:%S')))

結果

出力結果は以下。

START: 2020/0114 23:06:07

prime1 : 43.317183
prime0 : 0.229494
prime : 0.238351
is_prime1 / is_prime1 : 1.0
is_prime1 / is_prime0 : 188.7508300870611
is_prime1 / is_prime  : 181.73694677177775

END  : 2020/0114 23:06:50

コンテストで書いたものと、いま本気で書いたものは、微妙にコンテストで書いたもののほうが速い。

「自己最速の素数チェッカー」を実装しようとして、最速になりませんでした。

けどまあ、どっちもそこそこ速い。

おまけ

ちなみに、14桁の素数 67280421310721 で時間を確かめてみる。

(判定ロジックのループを完全に回してみる)

$ time python3 -c "from check import is_prime; is_prime(67280421310721)"

real    0m1.074s
user    0m0.953s
sys     0m0.047s

1秒ぐらい。

コンテストだと時間制限が2秒だから、半分強を素数判定に使ってる計算。

1<N<=14 の数字を使った素数判定問題が出ないことを祈ろう。