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

• 소수와 관련된 알고리즘은 두 가지가 있다.

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법
2. N보나 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 (N이하의 소수)

• 소수 : 약수가 1과 자기 자신밖에 없는 수
• N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

⇒O(N)

• N이 소수가 되려면, 2보다 크거나 같고 N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
• 이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문

( N=a x b로 나타낼 수 있는데, a가 작을수록 b는 크다.

 

가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.)

⇒O(N/2)

 

N이 소수가 되려면, 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안된다. (N이 소수가 아니라면, N=axb로 나타낼 수 있다.)

=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;
}

 

그러나, 위와 같은 방법보다 에라에라토스테네스의 체를 사용하면 가장 빠른 시간 내에 풀 수 있다.

//에라스토테네스의 체 이용
    bool isPrime[400000];
    for(int i=2;i<=400000;i++){
        isPrime[i] = true; //일단 다 소수임
    }
    for(int i=2;i<=400000;i++){
        for(int j=i*2;j<=400000;j+=i){
            if(isPrime[j]==false){
                continue;
            }else{
                isPrime[j]=false;//소수아님
            }
        }
    }

미리 문제에서 지정된 범위까지 소수를 구해놓은 이후에 그 범위 안에서 소수인것을 찾으면 된다.

 

2,4,6,8,10~~~~ 2의 배수들은 소수가 아니기 때문에 false이다.

범위를 다 돈 이후에는 3,6,9,12~~~ 3의 배수들에 한해 검사를한다.

남은 것만이 소수이다.