[SWEA|파이썬] 3131. 100만 이하의 모든 소수 (D3)-에라토스테네스의 체

문제

https://tinyurl.com/2l7j6bxz

SW Expert Academy

 

 

🐍파이썬

import math
sosu = [0 for _ in range(1000001)]
for i in range(2, int(math.sqrt(1000001))+1):
    if sosu[i] == 1:
        continue
    for j in range(i*2, 1000001, i):
        sosu[j] = 1

for i in range(2, 1000001):
    if sosu[i] == 0:
        print(i, end=" ")

백만까지의 수를 모두 소수판별해야 하는 문제이다.

시간초과를 대비하여 O(N^1/2)의 시간 복잡도를 가진 에라토스테네스의 체 알고리즘을 사용했다.

 

1️⃣ 0 ~ 1000000까지의 인덱스를 생성하고 모두 0으로 초기화한다.

2️⃣ 2부터 int(math.sqrt(1000001))+1까지 for문을 돌며 원소값이 1이면(=소수가 아님) 그냥 지나치고 원소값이 0이라면 i값의 2배부터 시작해서 1000000까지 간격 i를 두고 모두 방문해 i값의 배수 인덱스에 1을 대입해 소수가 아님을 표시한다.

👉 int(math.sqrt(1000001))+1까지만 확인하는 이유는, 어떤 수 n의 최대약수는 sqrt(n)이하이기 때문이다.(1과 자기자신을 제외하면)

ex)

n = 9, 9의 약수는 1, 3, 9

n = 10, 10의 약수는 1, 2, 5, 10

n = 36, 36의 약수는 1, 2, 4, 6, 9, 18, 36

이해가 안 간다면👉 이유를 더 자세히 설명해주는 블로그(https://tinyurl.com/2zl539h9)

에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유

👉 sosu[j] = 1 : i의 배수는 소수일 수 없으므로, i 자신을 제외한 모든 배수에 소수임을 체크해주는 것이다. 즉, i가 2인 경우 4, 6, 8, 10, ... 모든 2의 배수를 소수가 아니라고 표시하는 것

👉 for j in range(i*2, 1000001, i) : for문을 i 간격으로 돌리는 이유는 i의 배수 인덱스에 방문하기 위함이다.

👉 시작 인덱스가 i값의 2배인 이유는 2, 3, 5, 7과 같은 수는 소수가 아니므로, 그냥 i에서부터 소수가 아님 처리를 해버리면 2, 3, 5, 7까지 모두 소수처리가 된다. 이를 방지하기 위해 i*2에서부터 소수처리를 진행한다.

3️⃣ 소수판별이 끝난 arr를 방문해 원소값이 0인 인덱스(=소수 인덱스)만 출력한다.

 

 

참고

https://tinyurl.com/2gcxfrln

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전