[파이썬] 백준 2960번 「에라토스테네스의 체」

문제

 

문제분석

에라토스테네스의 체는 한참 알고리즘 공부할 때 소수 구하는 문제 부분에서 나왔었다. 2부터 시작하여, 2는 실수이므로 2를 제외한 2의 배수들은 모두 제거한다. 2보다 큰 숫자인 3도 실수이므로, 3을 제외한 3의 배수인 모든 뒤쪽의 수들을 전부 지운다. 다음 4는 이미 지워져있으므로 넘어가고, 5는 소수이므로 5를 제외한 모든 배수들을 지운다. 이를 반복하여 소수들을 구하는 것이 에라토스테네스의 체이다.

이도 마찬가지인데, 범위는 n, k를 입력받았을 때 n까지로 정해져있고, k번째로 지워진 수를 구하는 것이고 n의 수가 1000 보다 작으므로 이중포문으로 돌려도 충분한 자원으로 프로그램을 실행시킬 수 있을 것이다.

 

풀이 전략

이 중 for문 두 번 돌리면서 미리 선언된 배열에서 조건을 건들면서 개수를 세면 된다. 딱히 어려울 것은 없어보인다.

 

코드

 

 

결과

 

후기

시험기간이라 어려운 골드문제 다시 들어가기에는 좀 빡센 것 같고, 기존에 안 풀었던 내용들이나 풀면서 반복해야겠다