[에라토스테네스의 체] 소수를 찾는 방법 중 하나 [Python, 파이썬]

 

n = int(input())	# 어디까지 구할지

prime_check = [True] * (n+1)    # 소수의 배수들을 체크

for i in range(2, int(n ** 0.5) + 1):
    if prime_check[i]:
        for j in range(i*2, n + 1, i):  # 소수 자신을 제외한 배수에 체크
            prime_check[j] = False

prime_number = [i for i in range(2, n+1) if prime_check[i]] # 소수 리스트