[알고리즘] 에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체는 체라는 말처럼 무엇인가를 걸러내는 거나 판별하는 것을 의미하는데, 이것은 소수(PrimeNumber)이다. 소수는 2개의 약수(1과 자기 자신)만을 가지고 있는 수이다. 즉, 에라토스테네스의 체는 소수를 대량으로 빠르게 판별할 수 있는 알고리즘입니다. 먼저 일단 소수를 판별하는 방법을 구현해보겠습니다. #include using namespace std; //소수 판별 bool IsPrimeNumber(int x) { for(int i = 2; i < x; i++) { if(x%i ==0) retur false; } return true; } 위는 간단하게 소수를 구하는 방법이다. 하지만 시간복잡도가 O(N)로..
