素数判定の実装【Python】

単純に自身より小さな数で割ってみて、割れないばあいは素数と判定します。

def isPrime(n):
    for i in range(2, n):
        if n%i==0:
            return False
    if n==1:
        return False

    return True

for i in range(2,100):
    print(i,':',isPrime(i))

以下の改善を施した試し割り法の実装を紹介します。

• sqrt(n)までしか判定しなくて良い
• 偶数は必ず割り切れるため、2以外の偶数は必ず素数ではない（奇数のみ判定する）

import math

def isPrime(n):
    for i in range(3, math.floor(math.sqrt(n))+1, 2):
        if n%i==0:
            return False

    if n==2:
        return True
    if n%2==0:
        return False
    if n==1:
        return False

    return True

for i in range(2,100):
    print(i,':',isPrime(i))

エラトステネスの篩の詳細はこちらをご覧ください

以下、Pythonでのエラトステネスの篩の実装を紹介します。

import math

# n以下の素数判定のリストを返す
def eratosthenes(n):
    prime_list = [False, False] + [True]*(n-1)
    for i in range(2, math.floor(math.sqrt(n))+1):
        if not prime_list[i]:
            continue
        for j in range(i*2, n+1, i):
            prime_list[j] = False
    return prime_list

n = 10
l = eratosthenes(n)
for i in range(n+1):
    print(i,':',l[i])

# 0 : False
# 1 : False
# 2 : True
# 3 : True
# 4 : False
# 5 : True
# 6 : False
# 7 : True
# 8 : False
# 9 : False
# 10 : False