개요 백준 소수 문제들이 눈에 들어와서 푸는데,, 이 문제만 같은 방식으로 해결이 안되는 거다. 서칭한 결과 소수 구하기 문제는 시간초과를 주의해야 하고, 소수 문제에서 시간초과를 피하기 위해 에라토스테네스의 체라는 개념을 알아두면 유용하다는 결론을 내렸다. (하지만 공부한 결과 모든 소수 문제에 적용되는 것은 아니다..! 끝까지 글을 읽어보자) 📝 에라토스테네스의 체 에라토스테네스의 체란? 어떤 수 n 이하의 모든 소수를 찾는 간단하고 빠른 방법으로, 자기 자신을 제외한 배수를 모두 차례대로 지우는 방식이다. 더이상 지울 수 없을 때 남아있는 수들이 소수이다. 에라토스테네스의 시간복잡도는 O(n log(logn))이다. 에라토스네네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 ..