[백준 코딩테스트(Python)] 기본 수학 2 - 소수 구하기 (에라토스테네스의 체)

 

1929번: 소수 구하기

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다

 

---

1. 문제 접근 방식

이전에 풀었던 문제와 유사하게 코드를 짰는데 시간초과였다. 내가 선택한 방식은 i를 1부터 i까지 전체 범위의 수를 다 비교하는 것이다. i가 100이라면 1부터 100까지 모두 비교하는 방식이라 시간이 오래 걸릴 수 밖에 없다.

M, N = map(int, input().split())

sosu = []

for i in range(M, N+1):
    cnt = 0
    for j in range(1, i+1):
        if i % j == 0:
            cnt += 1
    if cnt == 2:
        sosu.append(j)

print(*sosu, sep = '\n')

 

고민 끝에 찾아보았고, 방법은 '에라토스테네스의 체'였다.

에라토스테네스의 체는 소수를 찾는 방법으로, 고대 그리스 수학자 에라토스테네스가 발견하였다.

 

2부터 소수를 구하고자 하는 구간의 모든 수를 나열하고 차례대로 자기 자신을 제외한 배수를 제거한다.

단, 자기자신은 소수 리스트에 추가한다. 이를 반복적으로 행하면 이 구간 내의 모든 소수가 남게 된다.

에라토스테네스의 체 (위키백과)

출처 : 위키백과

 

 

2. 풀이코드

# '에라토스테네스의 체' 알고리즘 활용

M, N = map(int, input().split())

for i in range(M, N+1):
    # 1은 소수가 아니므로 제외
    if i == 1:
        continue
    # 2부터 i의 제곱근까지만 소수인지 검증 → 빠르게 검증 가능
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            break
    else:
        print(i)

 

1) M이상 N이하의 소수를 반복문으로 하나씩 i로 가져온다. 이 때, M이 1일 수 있다. 1은 소수가 아니기 때문에 if문을 사용하여 i가 1이면 다음 반복문으로 넘어가도록 코드를 짜주자.

 

for i in range(M, N+1):
    # 1은 소수가 아니므로 제외
    if i == 1:
        continue

 

 

2) i가 소수인지 검증해야 한다. 이전에 내가 작성했던 코드는 1부터 i까지의 값을 모두 비교하여 소수인지 찾아내었다. 하지만 '에라토스테네스의 체' 알고리즘으로 풀어보면 2부터 i의 제곱근까지만 소수인지 검증하면 된다.

 

# 2부터 i의 제곱근까지만 소수인지 검증 → 빠르게 검증 가능
for j in range(2, int(i**0.5)+1):
    if i % j == 0:
        break
else:
    print(i)

 

 

❓ 왜 i의 제곱근까지만 검증하면 될까? (range(2, int(i**0.5)+1인 이유?)

나도 이 부분이 매우 궁금했으나 정작 알려주는 포스팅이 없어서 애먹었다ㅠ_ㅠ

예제를 살펴보자.

 

i = 12

i의 제곱근은 2√3으로 정수로 변경해주면 3.xx이 된다.

i의 약수 : 1, 2, 3, 4, 6, 12

1 x 12 = 12

2 x 6 = 12

3 x 4 = 12

 

 

i = 100

i의 제곱근은 10이다.

i의 약수 : 1, 2, 4, 5, 10, 20, 25, 50, 100

1 x 100 = 100

2 x 50 = 100

3

4 x 25 = 100

5 x 20 = 100

6

7

8

9

10 x 10 = 100

 

 

위와 같이 i의 제곱근까지만 확인을 해도 소수를 판단할 수 있다.

소수가 아닌 경우(i를 j와 나누었을 때 나머지가 0이 되는 수)의 몫(초록색)도 i의 약수가 된다. 그렇기에 제곱근까지만 확인을 해도 된다.

(좀 더 자세한 내용은 아래의 포스팅을 확인하면 좋다. 정말 설명을 잘해주셔서 많은 도움이 되었다.)

 

3. REFERENCE

백준 1929[소수 구하기] : 파이썬 & 시간초과 해결방법 & 소수 판정, 에라토스테네스의 체