(1929) 소수 구하기

https://www.acmicpc.net/problem/1929

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 6번째

 

 

 

에라토스테네스의 체를 기본적인 방법으로 구현하면 이미 소수가 아닌 것으로 결정된 값도 다시 탐색하는 등의 비효율적인 부분으로 인해 O(N log log N)의 시간복잡도를 가진다. 물론 이 코드를 써야 하는 문제라면 이 정도로도 충분하지만 오일러의 체 등을 써서 O(N)까지도 줄일 수 있다. 다만 실제로는 연산 비용, 캐시 미스 등의 문제로 오히려 느려지기도 해서 현실적으로는 비트 연산을 이용해 가벼운 연산으로 만드는 것이 가장 실전성 있다고 한다.

그래도 몇 가지 최적화 기법을 설명하자면...

1. 짝수는 2를 빼고 모두 합성수이므로, 예외 처리를 하고 체 검사나 정답 확인을 할 때 탐색 범위에서 제외해버릴 수 있다.

2. 소수 하나를 판단할 때와 마찬가지로 √n까지만 체크하면 된다. 어떤 합성수 n=pq에서 p가 √n보다 크다면 q는 √n보다 작으므로 이미 걸러졌기 때문이다.

3. 어떤 소수 p의 배수를 체에서 거를 때, p배수(p*p)부터 검사하면 된다. 그 이하의 합성수는 p보다 작은 소수로 이미 체에서 걸러졌기 때문이다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  int m, n;
  
  cin >> m >> n;
  
  bool soe[1'000'001]= {true, true, false, };
  
  for(int i=3;i*i<=n;i+=2){
    if(soe[i])  continue;
    
    for(int j=i;i*j<=n;j+=2)  soe[i*j]= true;
  }
  
  if(m<=2 && 2<=n)  cout << "2\n";
  for(int x=(m&1?m:m+1);x<=n;x+=2){
    if(!soe[x])  cout << x << "\n";
  }
  
  return 0;
}