(Python) 소수 구하기

N 이하의 소수를 구하는 코드

arr = [False, False] + [True] * (N-1)
for i in range(2, int((N+1)**0.5+1)):
    if arr[i]:
        for j in range(i * 2, len(arr), i):
            arr[j] = False

arr[0]은 무시해주기 위해 False를 집어넣고 1~N까지 True와 False를 이용해 소수를 구분한다. 즉, 총 자리수는 N+1개이다.