エラトステネスの篩を用いた素数の検出

開発環境

• Visual Studio Code (Version: 1.85.1)
• julia version 1.9.4

注意

この実装は動作はしますが最適ではないようです。より高速化した実装をコメント欄から頂いています。

コード

function sieve_of_eratosthenes(n::Int)::Vector{Int}
  is_prime = trues(n)  # 各数が素数であるかどうかを示す配列。初期値はtrue
  is_prime[1] = false  # 1は素数ではない

  # 2から√nまで繰り返す
  for i in 2:isqrt(n)
      if is_prime[i]
          # 現在の素数の倍数を非素数としてマーク
          for j in i^2:i:n
              is_prime[j] = false
          end
      end
  end

  # is_primeがtrueであるインデックスの数だけを抽出して、素数のベクトルを作成
  return [x for x in 1:n if is_prime[x]]
end

# 例: 100までの素数を見つける
N = 100
primes = sieve_of_eratosthenes(N)
println(primes)

出力

[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]

参考資料

• Julia 1.9 Documentation
• エラトステネスの篩