에라토스테네스의 체
-
에라토스테네스의 체알고리즘 이론/알고리즘 구현 2019. 8. 15. 18:55
에라토스테네스의 체 에라토스테네스의 체는 소수 관련 문제를 풀 때 가장 자주 사용되는 방법입니다. 소수란 '양의 약수를 두개만 가지는 자연수' 를 의미합니다. 이러한 소수를 대량으로 빠른 시간 내에 구하는 방법이 에라토스 테네스의 체 입니다. -지워지지 않는 수를 찾을때는 루트 n까지만 찾습니다. 소수 판정 알고리즘과 동일한 최적화. - 배수들을 지울 때 i*i에서 시작합니다. 2*i는 이미 2의 배수를 지워졌을때 지워 졌을것 3*i도 마찬가지 코드 ( C++ ) #include #include #include using namespace std; int n;// 소수인지 아닌지// IsPrime[i] = i 가 소수인가?bool IsPrime[101];void eratosthenes() {// 1로 I..