Sieve of Eratosthenes

고등학교 때 에라토스테네스의 체를 배웠던 것 같다. 사실 뭐 고등학교 수학에서 쓰일 일은 거의 없고 그 노가다를 할 만큼 시간이 많지 않기 때문에 별로 사용하진 않았다. 컴퓨터는 우리보다 단순 계산을 훨씬 잘하기 때문에 이 노가다를 맡겨도 된다. 하지만 조금 더 효율적으로 구현현할 필요가 있다. 에라토스테네스의 체는 어떤 수의 배수들을 모조리 지우는 방식으로 소수를 구한다. 공간 복잡도는 O(N), 시간 복잡도는 O(N*log(logN))로 구현할 수 있다. 코드는 다음과 같다. int n; vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++) { if (is_prime[i] && (long long)i * i <= n) { for (int j = i * i; j <= n; j += i) is_prime[j] = false; } } 카운트를 제곱근까지만 해서 개선...

원문링크 : Sieve of Eratosthenes