소수 구하기 알고리즘

소수 구하기 알고리즘

1. 기본적인 방법

bool solution1(int x) 
{
	if (x < 2) {	// 0, 1은 소수가 아님
    	return false;
    }
    
	for (int i = 2; i < x; ++i) {	
   		if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

2부터 자기자신보다 작은 수까지 하나 하나씩 x % i를 하여 나머지가 0이면 소수가 아니고, 나머지가 0이 되는 수가 없으면 소수이다. 하나씩 탐색하므로 큰 수일 경우 시간이 오래 걸린다는 단점이 있다.

2. 조금 더 개선된 방법 - 1
   위의 방법에서 i < x를 i < x / 2로 바꾼다.
   예를들어 소수가 아닌 18의 경우 약수가 1 2 3 6 9 18 인데 여기서 1과 18을 제외하면
   2 3 6 9 이다. 1을 제외한 수로 나누어져야 하므로 x / 2까지만 탐색해도 무관하다.

bool solution2(int x) 
{
	if (x < 2) {	// 0, 1은 소수가 아님
    	return false;
    }
    
	for (int i = 2; i < x / 2; ++i) {	
   		if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

3. 위의 방법들보다 훨씬 더 개선된 방법
   100 이라는 숫자의 약수를 생각해보자
   1 2 4 5 10 20 25 100 이렇게 있다. 여기서 1과 100 을 빼고 생각해보자
   2 4 5 10 20 25 100 이다. 약수는 이렇게 2 * 50 = 100, 4 * 25 = 100 이런식의 a * b = x 이런식으로 이루어지기 때문에 sqrt(x)까지만 나누어봐도 소수인지 아닌지 판단할 수 있다. a와 b는 반드시 x의 제곱근보다 작거나 같기 때문이다.
   만약 x가 10000이면 100번만 탐색하면 되고, 숫자가 클 수록 탐색시간은 엄청나게 줄어들게 된다.
   주의할 점은 이 경우에는 i <= sqrt(x)이렇게 해줘야 한다.
   만약 위처럼 i < sqrt(x)이런식으로 해주면 25나 9 같은 경우에 소수가 아니라고 판단하기 때문

bool solution3(int x) 
{
	if (x < 2) {
    	return false;
    }
    
    for (int i = 2; i <= sqrt(x); ++i) {
    	if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

i <= sqrt(x) 대신 i * i <= sqrt를 써도 무방하다. 하지만 i * i는 for문을 돌때마다 i * i계산을 해야하는 단점이있다.

4. 에라토스테네스의 체
   유명한 소수 구하기 알고리즘이다. 위의 세방법보다 훨씬 빠르고 구현하기도 어렵지 않다.

• 아이디어

1. 2부터 소수를 구하고자 하는 모든 수를 나열한다.(배열로 구현)
2. 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 한 칸 이동해서 그 수가 지워지지 않는 수라면 그 수의 배수를 모두 지운다.
4. 지워지지 않은 수는 소수이다.

위의 아이디어를 그림으로 나타내면 아래와 같다. 출처 위키백과

위의 경우 120까지의 소수를 찾는 것이므로 sqrt(120)인 11의 배수까지만 없애도 충분하다.

bool primeArray[MAX];	// MAX 구하고자 하는 수의 최댓값

void initPrime(int n) 
{
    fill(bool, bool + n, true);	// 처음엔 모두 소수로 본다.
    
    for (int i = 2; i * i <= n; ++i) {
    	if (primeArray[i]) {
        	for (int j = i * i;j <= n; j += 1) {
            	primeArray[j] = false;
            }
        }
    }
    
}

bool solution4(int x) 
{
    if (x < 2) {
    	return false;
    } 
    
    initPrime(1000000);
    
    return primeArray[x];
}

알고리즘 문제를 풀때 소수를 찾아야하는 경우가 있다면 에라토스테네스의 체를 사용하자!