에라토스테네스의 체

에라토스테네스의 체

1부터 n까지의 수들을 소수판별하는 코드이다.

n = int(input())

check = [False, False] + [True]*(n-1) 
prime = []

for i in range(2,n+1):
    if check[i]:
        prime.append(i)
        for j in range(i+1,n+1):
            if j%i == 0:
                check[j] = False

print(prime)

i가 2일 때, 2의 배수들을 전부 False로 만들어준다. 그리고 2를 소수로 넣는다.
i가 3일 때, 3의 배수들을 전부 False로 만들어준다. 그리고 3을 소수로 넣는다.
i가 4일 때는 check[4]가 False이기 때문에 if문 성립 x
이를 i가 n일 때까지 반복하면 prime 리스트에는 소수가 담기게 된다.

<2024-01-19(수정)>
하지만 위의 코드는 if j%i == 0:이 연산을 range(i+1,n+1)만큼 계속 반복하므로 비효율적이다. 그냥 i만큼을 계속 더해주면서 False 처리를 해주는 것이 더 효율적이다.

n = int(input())

check = [False, False] + [True]*(n-1)
prime = []

for i in range(2,n+1):
    if check[i]:
        prime.append(i)
        for j in range(i*2,n+1,i):
            check[j] = False

print(prime)