에라토스테네스의 체
-
[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)알고리즘/수학 2018. 11. 27. 13:58
문제링크 : https://www.acmicpc.net/problem/1929 이 문제는 간단한 소수 구하기 소스로 구한다면 굉장히 오랜 시간이 걸리고 시간 초과가 발생하는 문제다. 이문제의 입력되는 수의 범위는 1 ~ 1,000,000 인데 기존 소수 구하는 방식은 2 ~ N-1 까지 반복하면서 나누어 지는 수가 있는지 판단하는 소스 였다. 그럼 최악의 상황에서 1에서 1,000,000 까지 구해야 한다면 상상할 수 없는 연산 수가 발생한다. 이렇게 큰 수들에도 소수가 있을거고 그럼 이 큰 수들을 소수인지 판별하는 방법도 있을것이다. 그게 바로 에라토스테네스의 체 라는 방식인데 노가다라 비효율적인 방식이라고는 하는데 지금 문제에는 제일 적합한 방식이다. 출처 : wiki 백과 에라토스테네스의 체를 구하..