[Python] [SWEA] 3131. 100만 이하의 모든 소수

3131. 100만 이하의 모든 소수

(로그인 해야 됨)

 

1 이상 100만(106) 이하의 모든 소수를 구하는 프로그램을 작성하시오.

참고로, 10 이하의 소수는 2, 3, 5, 7 이다.

[입력]

이 문제의 입력은 없다.

[출력]

1 이상 100만 이하의 소수를 공백을 사이에 두고 한 줄에 모두 출력한다.

 

---

해결 Point: 에라토스테네스의 체 사용

 

에라토스테네스의 체:

소수는 저장하고, 소수의 배수들은 지워나간다.

 

# 3131. 100만 이하의 모든 소수
import math

arr = [True for _ in range(1000001)]    # 처음엔 모든 수가 소수인 것으로 초기화

# 에라토스테네스의 체 알고리즘: 배수를 지운다.
for i in range(2, int(math.sqrt(1000000))+1):   # 2부터 n의 제곱근까지의 수를 확인
    if arr[i] == True:  # i가 소수인 경우(남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i*j <= 1000000:   # 일일히 반복하면서 지운다
            arr[i*j] = False
            j += 1

for i in range(2, 1000001):
    if arr[i]:  # 소수라면 출력
        print(i, end=' ')

 

코드 분석:

1. 먼저 확인할 범위 만큼의 배열을 만들어 True로 채운다 (index는 수로, True는 조건문에서 사용)

 

2. 2~확인할 범위의 제곱근 까지의 수를 확인한다.

제곱근까지만 확인하는 이유는 약수는 제곱근을 중심으로 대칭을 이루기 때문에

수를 2부터 제곱근까지 나누었을 때 나누어 떨어지는 약수가 존재한다면

소수가 아닌 것을 바로 알 수 있기 때문이다.

 

3. arr[i]가 True인 것은 해당 index가 소수라는 뜻이다.

i = 2 부터 확인하고 있는데, 그 안에 j = 2, j += 1 로 설정하여,

그 다음부터의 배수들은 소수가 아니므로 False로 변경해준다.

반복은 index만큼 i*j < 1000000 범위로 설정한다.

 

4. 위 반복을 거치면 소수가 아닌 것들은 False로 바뀐다.

True는 다 소수이므로 True인 것들의 index를 출력한다.

 

Point:

1. 범위만큼의 index를 True로 채운 배열을 먼저 생성했다.

2. 제곱근까지만 확인하여 확인 범위를 줄여 속도를 높였다.

3. 소수의 배수인 것들을 False로 제외 시켰다.

4. index가 수이고, True가 해당 수는 소수, False는 소수가 아님을 의미한다.