언제나 내 코드는 worst case에 걸려 시간 초과를 면치 못한다.
이전에 이 코드로 소수 찾기 문제를 풀면, 시간초과 이슈 없이 해결했는데 이번엔 에라토스테네스의 체를 활용하기를 문제에서 원하고 있고, 더 효율성 좋은 코드를 활용하길 바랬다.
포인터를 2개 활용해서 소수를 찾는 과정은 배열에서 2개의 포인터를 활용해 target element를 찾는 것과 상당히 동일해서 Nested Loop를 사용했지만, 결과적으로 ‘시간 초과’ 가 발생했다.
사실 한 번에 통과할 거라곤 생각하지 않았고, ‘에라토스테네스의 체’라는 걸반드시 활용해야한다고 하기에 정리하는 글이다.
에라토스테네스의 체를 활용하면 가장 큰 장점은 ‘자연수’를 거름망으로 활용해서 걸러낸 ‘소수’들을 남겨주기에 대량의 소수를 판별할 때 아주 효율적인 알고리즘으로 평가받는 것 같다.
모범 답안
이 코드는 다른 사람이 해당 문제에 에라토스테네스의 체 코드를 응용해 작성한 방법이다.
사실 다 이해 되는데 딱 한 구간, num ** 0.5 라고 작성한 부분이 제일 이해가 안됐다.
여기서 왜 갑자기 제곱근까지의 값을 비교하면서 찾았을까?
그 해답은 사실 위키피디아에 있는 에라토스테네스의 체 모범 답안에 있었다.
위키피디아에 올라온 에라토스테네스의 채 코드
어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N**0.5) == O(NlogN)의 시간 복잡도로 빠르게 구할 수 있다고 일부 블로그에서 설명을 하고 있다.
이와 관련해 다른 블로그들의 설명을 충분히 찾아보면서 글을 작성하고자 했고,
소수는 소수 N의 제곱근 보다 크지 않은 어떤 소수로도 나눠지지 않기 때문에 제곱근을 이용하면 1과 자신을 제외한 (N-2) 의 루트 만큼으로 연산 횟수가 크게 줄어드는 것입니다.
라고 한다. 즉, 쉽게 풀어 설명하면 제곱근 보다 작은 수의 범위 내에서 주어진 수 N의 약수가 있다면, 그 값은 틀린 값이다.
중, 고등학교 때 공부할 때도 에라토스테네스의 체를 배우지는 않은 것 같아서 프로그래밍 배울 때 뜬금 없이 나타난 것 같은데 활용도가 무척 높다.
사실 프로그래밍 자체가 문제는 다양하게 출제할 수 있어도, 결국에 해당 문제를 추상화하게 되면, 거의 비슷한 패턴으로 만들어진다.
문제에 있는 패턴을 발견하는 것은 매우 중요하다.
다음 소수 관련 문제를 접하고 대량의 소수를 처리할 일이 있다면 ‘에라토스테네스의 체’를 꼭 다시 활용해보자.
Ryan
