소수 구하기(에라토스테네스의 체)

소수란 약수가 1과 자기 자신밖에 없는 수를 말한다.

 

소수는 이러한 특성 때문에 RSA와 같은 암호학 분야에서 널리 쓰인다.

 

또한 매미는 천적과 같은 매미끼리의 먹이 경쟁을 피하기 위해 5, 7, 13년의 주기를 가지고 땅 밖으로 나온다고 알려져 있다.

 

심지어 소주의 용량도 나누어 떨어지지 않도록 약 7잔이 나오도록 설계되어있다!(믿거나 말거나)

 

각설하고 소수를 구하는 방법에 대해서 알아보자! 

 

우선 약수가 1과 자기 자신 밖에 없는 수인 소수를 구하기 위해서는 

 

어떠한 수 N이 주어질 때, N이 소수가 되려면 이 N을 2부터 N-1까지의 수로 나누어 떨어지면 안된다는 것을 알 수 있다.

 

단순하게 생각해보면 2부터 N-1까지 약 O(N)의 시간 복잡도로 소수를 구할 수 있다.

 

bool prime(int n){
	if(n < 2) 
    {
    	return false;
    }
    for(int i=2; i<=n/2;i++)
    {
   		 if(n % i == 0)
         {
    	  return false;
         }
    }
    return true;
}

위의 코드에 n/2로 돼있는 것은 

 

N의 약수 중 가장 큰 것은 N/2보다 작거나 같기 때문이다.

 

N= a x b로 나타낼 수 있다. (a중 가장 작은 값은 2이므로, b는 N/2를 넘지 않는다.)

 

또한 a>b라면 두 수를 바꿔 항상 a<=b로 만들 수 있기 때문에 

 

O(루트 N)으로 가능하다. 

 

bool prime(int n){
    if(n < 2) 
    {
    	return false;
    }
    for(int i=2; i*i<=n;i++)
    {
    	if(n % i == 0)
        {
        	return false;
        }
    }
    return true;
}

 

하지만 n개의 소수를 매번 위와 같은 알고리즘으로 구하게 되면 O(N*루트 N)의 시간 복잡도가 든다.

 

이를 위해 에라토스테네스의 체를 참고해보자.

 

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 것으로 소수를 찾기 위해 체에 걸러 내는 알고리

즘을 뜻한다.

 

에라토스테네스의 체(위키백과)

 

2, 3, 5, 7을 제외한 2, 3, 5, 7의 배수들을 모두 체에 거른다(지운다)

 

위의 예시 이미지에서는 120까지만 구하기 때문에 11보다 작은 배수들만 지워도 충분하다.

 

void Eratos(int n){

    if(n<=1) return;
    
    bool* checkArray = new bool[n+1]; 
    
    for(int i=2; i <= n; i++)
    {
    	checkArray[i] = true; //true로 초기화
    }
    
    for(int i=2; i*i<=n;i++) //루트 N까지만 검사
    {
    	if(checkArray[i])
        {
            for(int j=i*2;j<=n;j+=i)//체에 거른다.(배수들 제거)
            {
            	checkArray[j] = false;
            }
        }
    }
}