[BOJ]2960. 에라토스테네스의 체

문제:

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

 

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

 1. 2부터 N까지 모든 정수를 적는다.

 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.

 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.

 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

입력:

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

출력:

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

풀이방법:

우선 N까지 수가 있는 배열을 만들고 이를 에라토스테네스의 체 규칙에 따라서 하나씩 지워나간다. 이 때마다 하나씩 count를 늘려주면서 K번째가 되면 현재 지운 값을 출력하도록 한다.

def make(i):
    global answer
    idx=i
    count=1
    temp=0
    while idx*count <len(numbers):
        temp=numbers[idx*count]
        if numbers[idx*count]!=0:
            numbers[idx*count]=0
            answer+=1
            if answer==k:
                break
        count+=1
    return temp
 
 
n,k=map(int,input().split())
numbers=list(range(n+1))
numbers[1]=0
answer=0
conti=True
while conti:
    for i in range(len(numbers)):
        if numbers[i]!=0:
            temp=make(i)
            if answer==k:
                print(temp)
                conti=False
                break

문제링크:

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