[Python] BOJ(백준) 2960번 - 에라토스테네스의 체

링크

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

난이도(solved.ac 참고)

실버4

풀이

쉬운 문젠데, 에라토스테네스의 체의 개념을 메모해두기 위해 포스팅한다.

 

에라토스테네스의 체는 N 아래의 소수를 빠르게 구하는 방법으로, 2부터 N까지의 인덱스가 True로 되어있는 배열들에 대해 i에 해당하는 값을 소수 배열에 넣은 뒤 그 i의 자연수 배수의 값들을 하나씩 False로 만들어주는 방식으로 소수를 구하는 방법이다.

 

예를 들어 2를 primes 배열에 넣는다면, 자연수 배수인 4, 6, 8, ... 의 값들을 모두 False 처리를 해주는 것이다.

 

이 문제는 K번째로 지워지는 수를 구해야 되었기 때문에 우선 result라는 배열에 지워질 값들을 전부 넣고 k-1번째 인덱스의 값을 출력하게끔 하였다. 근데 시간복잡도가 O(N^3)이나 되어서. 다른 코드를 다시 생각해봤다.

 

count라는 변수를 정한 뒤 False 처리를 해줄 때마다 count 값을 1씩 증가시키는 것이다. 지워지는 수가 2, 3, 5, 7등 소수든 소수의 배수든 상관없이 반복문 돌때마다 count 값에 1씩 더해줬다. 이 값이 k가 되면 그 순간의 값을 출력하고 끝내는 방식으로 진행했다. O(N^2)로 줄였을 뿐만 아니라 불필요하게 배열을 만들지도 않아서 시간 복잡도가 더 개선되었다.