エラトステネスの篩

Sieve of Eratosthenes

エラトステネスの篩です。
このfor文の書き方に初めて触れたのでそこに難儀しました...。
余談ですがPythonのforループって遅いらしいですね。色々と理由は目にしますが、なんでなんでしょうね。
動的型付けでループのたびに型チェックやってるからとかイテレータを使ってるからとか様々な要因はあるんでしょうが...。


# coding: utf-8
# geschrieben von Beliar698ma

import math

def sieveOfEratosthenes():

  try:
    n = int(input('Please input a number:'))
  except ValueError:
    print('Please input a VALID integer.')
    return
  
  if n <= 1:
    print('Please input a number greater than 1.')
    return

  # 真偽値表の作成...インデックスと検査する値が一致するように

  is_Prime = [False, False] + [True] * (n - 2)
  lim = int(math.sqrt(n)) + 1

  for i in range(2, lim):
    if is_Prime[i]:
      for j in range(i * i, n, i):
        is_Prime[j] = False
  
  primes = [i for i, prime in enumerate(is_Prime) if prime]

  print(primes)


sieveOfEratosthenes()