[알고리즘]백준 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번째 지워진 수를 출력한다.

 

풀이 

---

에라토스테네스의 체를 활용해봅시다 

확인하고 싶은 범위 N까지의 숫자+1까지의 원소를 가지는 배열을 만들어주겠습니다 

배열의 원소는 기본적으로 전부 True가지게 만듭니다 

이때 배열의 index는 소수인지 아닌지 판단할 숫자와 같습니다 

 

True의 의미는 소수, False는 합성수입니다 

 

원리는 다음과 같습니다 

만약 숫자 a가 True라면(소수라면)  a의 배수인 2a, 3a.... ka(ka는 N보다 작거나 같은 숫자)는 자연스럽게 합성수가 됩니다 

이를 반복문을 통해 구현해줍니다 

 

문제에서는 K번째 숫자를 출력하는 것이므로 하니씩 업데이트를 해주면서 cnt를 더해줍니다  

from sys import stdin

N, K = map(int, stdin.readline().strip().split())
def prime_sieve(N, K):
    
    arr =[True for i in range(N+1)]
    arr[0], arr[1]=False, False
    cnt=0 
    for i in range(2,N+1):
        if arr[i]==True:
            j=1
            while i*j<N+1:
                if arr[i*j]==True: 
                    cnt+=1
                arr[i*j]=False
                if cnt==K:
                    return i*j 
                j+=1
print(prime_sieve(N,K))