[알고리즘] 백준 2960 파이썬 - 에라토스테네스의 체

 

2960번: 에라토스테네스의 체

문제

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

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

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

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

 

 

문제풀이

#01
n,k= map(int,input().split())
arr=[]
sosu=[False,False]+([True]*(n-1))
cnt=0
#02
for i in range(2,n+1):
    for j in range(i,n+1,i):
        if(j not in arr):
            arr.append(j)
            cnt+=1
        #03
        if(cnt==k):
            print(j)
            quit()

- 에라토스테네스의 체 설명은 아래 링크를 참조

[알고리즘] 백준 17103 파이썬 - 골드바흐 파티션(에라토스테네스의 체)

- #01 : 문제에서 주어진 입력을 저장해주고, sosu와 arr,cnt를 정의해준다.

- #02 : for문을 통해 2의 배수부터 시작하여 n까지 모두 제거하기 시작한다.

           arr에 제거한 값을 추가한다. (제거한 값을 다시 제거하는 것을 방지하기 위해)

           제거하였다면 cnt에 1을 더해준다. 

- #03 : 만약 cnt값이 k와 같다면 그 당시의 j값을 출력하고 코드를 종료한다.