2960.에라토스테네스의 체

2960.에라토스테네스의 체 문제 바로가기

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

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

2부터 N까지 모든 정수를 적는다.
아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

문제 접근

• N보다 작거나 같은 모든 소수를 찾는 알고리즘
• 지운 순서를 찾으므로 > false로 이루어진 list를 true로 바꿔가면서 지운다.

첫번째 풀이

import sys
input = sys.stdin.readline

a,b = map(int,input().split())
list=[]
new_list=[]
for i in range(2,a+1):
    list.append(i)
while len(list) != 0:
    n = 1
    k = min(list)
    while True:
        if k*n in list:
            list.remove(k*n)
            new_list.append(k*n)
            print(list)
        n += 1    
        if k*n in list and k*n in new_list:
            break    

print(new_list)
print(new_list[b-1])

두번째 풀이 : True list를 활용해서 False로 바꿔가며 체크

tmp=0에서 True>False로 바뀌는 횟수를 세다가 tmp == K가 되는 시점의 j값을 출력한다

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
tmp = 0
list = [True] * (N + 1)
for i in range(2, N + 1):
    for j in range(i, N + 1, i):
        if list[j] != False:
            list[j] = False
            tmp += 1
            if tmp == K:
                print(j)

추가 메모

• 반복문으로 리스트 만들기

a = [i for i in range(10)]        # 0부터 9까지 숫자를 생성하여 리스트 생성
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

list = [True] * (N + 1)
list를 그 수만큼 곱해서 구할 수도 있다.

• 이미 제거한 수를 기록할 필요는 없음.