[백준 알고리즘] 2940번: 에라토스테네스 체 (Python)

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

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())
a = [0] * (n+1) # 지워지지 않은 수인지, 지운 수인지를 체크하기 위한 리스트
cnt = 0 

for i in range(2,n+1): # 2부터 n+1까지
  for j in range(i,n+1,i): # i부터 n+1까지 i의 배수만큼 
    if a[j] == 0: # 아직 지워지지 않았으면 지우고, cnt + 1
      a[j] = 1
      cnt += 1
      
      if cnt == k:
        print(j)

 

풀이

N보다 작거나 같은 모든 소수를 찾는 에라코스테네스 체 문제입니다. 

 

수를 하나씩 지워나가기 위해서는 이미 지워진 수인지 아닌지를 판별하는 리스트를 만들어야 합니다. 

그 후 반복문을 돌면서 해당 수의 값이 0이면 1로 만들어 그 수를 지워주고, cnt를 1씩 증가시킵니다

 

이러한 과정을 반복하고, cnt가 입력받은 k와 같아질 때 값 j를 출력해줍니다. 

 

for j in range(i(시작 값),n+1 (끝 값),i(얼마만큼): 

만약 i에 2, n에 10이 들어온다면 j는

2 -> 4 -> 6 -> 8 -> 10. 즉 i의 배수만큼 수를 건너 뛰어 만들어집니다.