素数の判定

与えられた数 n が素数なら True,そうでなければ False を返す関数を作ってみましょう。

基本は順に割っていけばよいはずです。

def isprime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

動作確認してみましょう。

for i in range(2,100):
    if isprime(i):
        print(i, 'は素数')

上は 2 以上 n 未満の整数すべてで割ってみました。もっと節約できるでしょうか。

import math

def isprime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0: return False
    return True

いろいろ改良ができそうです。例えば 2 を除けば偶数で割ってみる必要はないので,計算量は半分にできます。

import math

def isprime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0: return False
    return True

今日(例えば 20190823)は素数か?

import time

n = int(time.strftime('%Y%m%d', time.localtime()))
isprime(n)

math.sqrt() は平方数については正確な平方根を与えるはずですが,浮動小数点数の精度を超える整数の場合は心配です。整数の平方根を整数の範囲で求める次の isqrt() を使えば万全です:

def isqrt(n):
    if n == 0:
        return 0
    x, y = n, (n + 1) // 2
    while y < x:
        x, y = y, (y + n // y) // 2
    return x

これを使った関数:

def isprime(n):
    if n < 2:
        return False
    for i in range(2, isqrt(n)+1):
        if n % i == 0:
            return False
    return True

もっと大きい数の素因数分解をするには,SymPy の数論ライブラリが便利です。

import sympy

sympy.factorint(5040)
# ==> {2: 4, 3: 2, 5: 1, 7: 1}

sympy.factorint(20190823)
# ==> {20190823: 1}

sympy.isprime(20190823)
# ==> True

Last modified: