백준(Python) 풀이/수학

백준(Python) 2960번 에라토스테네스의 체 풀이

개발윗미 2021. 10. 12. 19:24

Python으로 구현한 2960번 에라토스테네스의 체 문제 풀이입니다.

 

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

 

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

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

www.acmicpc.net


n, k = map(int, input().split())

data = [True for i in range(n + 1)]
count = 0

for i in range(2, len(data) + 1) :
  for j in range(i, n+1, i) :
    if data[j] :
      data[j] = False
      count += 1
      if count == k :
        print(j)
        break

 

초기에 n개의 data 리스트의 값들을 모두 True로 설정한다.

 

이중 for문을 통해 해당 값이 True일 경우 해당 값을 False로 갱신한다. 그 후 count를 1씩 증가시키는데,

 

만약 count 값이 입력받은 k 값과 같을 경우 k번째 지우는 수를 출력한다.