【Python】素数を列挙するアルゴリズム

令和6年度 秋期 応用情報技術者試験 午後 問3「素数を列挙するアルゴリズム」を Python で記載してみた。

本問では，配列の要素番号は 1 から始まり，要素数が 0 の配列を {} で表されているが，Python では配列の要素番号は 0 から始まることに留意する。

2 以上の自然数 N に対して，全ての素数を発見するためのアルゴリズムとしてエストラウスの篩 (Sieve of Eratosthenes) が知られている。

関数 prime1

2 以上の自然数 N に対して，N 以下の素数を列挙する関数 prime1 のプログラムを示す。

def prime1(N):
    primes = []
    d = 2
    counter = 0
    while (d <= N):
        isPrime = True
        t = 2
        while (t < d):
            if (d % t == 0):
                isPrime = False
            t = t + 1
            counter += 1
        if (isPrime == True):
            primes.append(d)
        d = d + 1
    return primes, counter

N = 100
print(prime1(N))

関数 prime1 のコードを実行した結果を示す。

([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 4851)

N = 100 の場合，実行回数は 4,851 回である。

関数 prime2

素数の定義によって，2 以上の自然数 s について，s 自身を除く s の正の倍数 u は，1 と u 以外にも s も約数に含むので素数ではない。この性質を利用して関数 prime1 を改良し，次の手順で素数を列挙する関数 prime2 を考える。

(1) 2 以上 N 以下の自然数について，全て “素数” であるとマークする。

(2) 2 以上 N 以下の自然数 d について，次の a.，b. を行う。

1. d が “素数でない” とマークされている場合，何もしない。
2. d が “素数である” とマークされている場合，次の処理を行う。
   1. d が素数であることを確定させる。
   2. d 以上の自然数 x について，d を x 倍した数を “素数ではない” とマークする。

関数 prime2 のプログラムを示す。

def prime2(N):
    primes = []
    isPrime = [False]
    c = 1
    d = 2
    counter = 0
    while (c < N):
        isPrime.append(True)
        c = c + 1
    print(len(isPrime))

    while (d - 1 < N):
        if (isPrime[d - 1] == True):
            primes.append(d)
            t = d * d
            while (t <= N):
                isPrime[t - 1] = False
                t = t  + d
                counter += 1
        d = d + 1
    return primes, counter

N = 100
print(prime2(N))

関数 prime2 のコードを実行した結果を示す。

([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 104)

N = 100 の場合，実行回数は 104 回である。

関数 prime3

4 以上の偶数は全て 2 の倍数であるので素数ではない。したがって，2 以外の素数を列挙するためには奇数だけを考慮すればよい。この性質を利用して，関数 prime2 に次の変更を加えた関数 prime3 を考える。

1. 関数の戻り値として素数の一覧が格納される primes にあらかじめ 2 を格納しておく。
2. いずれのループも奇数についてだけ実行されるようにする。
3. 3 以上の自然数 2k+1 が素数か否かを isPrime[k] で表すようにする。

関数 prime3 のプログラムを示す。

def prime3(N):
    primes = [2]
    isPrime = []
    c = 2
    d = 3
    counter = 0
    while (c < N):
        isPrime.append(True)
        c = c + 2
    print(len(isPrime))

    while (d - 1 < N):
        if (isPrime[int((d - 2) / 2)] == True):
            primes.append(d)
            t = d * d
            while (t < N):
                isPrime[int((t - 2) / 2)] = False
                t = t  + 2 * d
                counter += 1
        d = d + 2
    return primes, counter

N = 100
print(prime3(N))

関数 prime3 のコードを実行した結果を示す。

([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 28)

N = 100 の場合，実行回数は 28 回である。

実行回数

N を横軸とした関数 prime1 ～ prime3 それぞれの実行回数を縦軸に示す。

参考文献

• 午後問題対策 プログラミング｜目指せ！応用情報技術者