Pythonで素数の個数を数える方法｜エラトステネスの篩による実装を解説

上限値 n が与えられたとき、2からnまでの範囲に存在する素数の個数を数えることを考えます。例えば、n = 10 の場合、結果は 4 となります。これは、10 未満には 2、3、5、7 という4つの素数が存在するためです。

この問題は「エラトステネスの篩（ふるい）」と呼ばれる古典的なアルゴリズムを使うことで、効率的に解くことができます。以下の手順に従って実装していきましょう。

• count を 0 で初期化する
• サイズ n+1 の配列 prime を作成し、すべて False で埋める
• i = 0 から n まで以下を繰り返す
  • prime[i] が False の場合
    • count を 1 増やす
    • j = 2 とする
    • j × i < n の間、以下を繰り返す
      • prime[i × j] を True にする
      • j を 1 増やす
• 最後に count を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        primes = [False for i in range(n+1)]
        for i in range(2,n):
            if primes[i] == False:
                count+=1
                j = 2
                while j*i<n:
                    primes[j*i] = True
                    j+=1
        return count
ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

入力

n = 50
n = 10

出力

15
4

コードの解説

このプログラムでは、まず n+1 のサイズを持つブール型のリストを作成し、すべて False で初期化します。False は「まだ素数かどうか判定されていない」状態を表しています。

次に、i を 2 から n-1 まで順番に確認していきます。prime[i] が False のまま残っていれば、i はそれより小さいどの数の倍数でもない、つまり素数であることが分かります。そこで count を 1 増やしたうえで、i の倍数をすべて True（合成数）としてマークしていきます。

このようにして、n = 50 の場合は 15 個、n = 10 の場合は 4 個の素数が正しくカウントされます。計算量は O(n log log n) となり、単純な全探索よりもはるかに高速に動作するのが特徴です。