[python] 백준 2960. 에라토스테네스의 체

문제

https://www.acmicpc.net/problem/2960

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

---

풀이

원래는 다른 문제를 풀려고 했는데, 에라토스테네스의 체 알고리즘으로 소수를 구하는 부분에서 막혀서... 그 부분부터 해결할까 싶어 아예 에라토스테네스만으로 푸는 문제를 하나 골랐고 그게 바로 이거다!

 

문제는 말 그대로, 에라토스테네스의 체의 방식으로 문제를 풀고 멈춰! 라고 했을때 어느 숫자를 지우고 있었는지를 묻는 문제였다.

 

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
result = 0

sosu = [True] * (n+1)
for i in range(2, n+1):
    for j in range(i, n+1, i):
        if sosu[j]:
            sosu[j] = False
            result += 1
            if result == k:
                print(j)

 

풀이코드는 이것! 

https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체

이 링크를 참고해서 코드를 작성했다. 에라토스테네스의 체는

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 

...

이걸 반복하는 방식이다. 이때 제거 방식은 True, False로 진행해서 코드를 작성해주면 된다. 내가 이해하기 쉬운 방식으로 코드를 다시 짜보자면...

import sys
input = sys.stdin.readline

n = int(input().strip())
result = []

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

print(result)

 

이렇게 할 수 있을 것 같다!!

신기했던 건... True, False로 해결보는 거? 이제 이 문제를 풀게 되었던 문제를 풀러 가봐야겠다..

그전에 시간 복잡도!!

 

시간복잡도

시간복잡도는... O(n log log n) 이거 일 것 같다.