[Python] 에라토스테네스의 체

소수를 구하는 알고리즘으로는 여러 방법이 있겠지만,

수학적으로나 공학적으로나 널리 사용되는 에라토스테네스의 체를 파이썬으로 간단히 구현해봤습니다.

n = int(input())

a = [0] * (n+1) # 0을 초기값으로 하는 배열을 생성합니다.
cnt = 0 # 소수의 개수를 카운팅하는 변수입니다.

for i in range(2, n+1):
  if a[i] == 0:
    cnt += 1
  for j in range(i, n+1, i):
    a[j] = 1 # i의 배수를 1로 변경합니다.

print(cnt)

아마도 보다 간명하고 퍼포먼스도 좋은 방법이 있을 것 같네요 ^^