[Algorithm][math] 소수, 에라토스테네스의 체

[Algorithm][math] 소수, 에라토스테네스의 체

소수 (prime)

약수가 1과 자기 자신 밖에 없는 수  (1은 소수가 아니다)

n이 소수가 되려면, 2보다 크거나 같고, n - 1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

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

하지만 이는 n이 클 수록 연산량이 많아 시간이 오래 걸린다.

예를 들어, 문제에서 m개의 수의 소수 판별을 할 필요가 있다면 m번 마다 isprime() 함수를 호출하게 되고 

isprime은 2부터 그 수(n)까지의 반복문을 실행할 것이다.

따라서 연산량이 매우 많다.

매번 수를 소수인지 판별하지 말고

소수를 저장해 놓고 사용하는 것이 더 빠르다.

이러한 경우 에라토스테네스의 체를 이용하여 소수 여부를 한번에 배열에 저장해 놓으면 연산 시간을 줄일 수 있다.

에라토스테네스의 체

* int prime[n] -> 1 : n이 소수, 0 : n은 소수가 아니다.

1. 2부터 n까지 모든 수 배열값은 1로 초기화 해 놓는다.

2. 2부터 i * i <= n 까지 반복

-> i를 root(n)까지 반복

수 n이 소수가 아니라면 n = a x b (a <= b) 이며 a와 b의 가장 차이가 작은 경우는 a == b인 경우이다.

즉, 다시말하면 a의 배수를 검사하는 동안 b의 배수 또한 같이 검사가 되는 것

따라서 가장 차이가 적은 root(n)까지만 검사를 하면 된다.

3. i의 배수를 모두 0으로 고친다.

-> i의 배수는 약수로 i를 가지기 때문에 소수가 아니다.

4. 추가로 i의 배수를 찾아가기 전에 prime 배열의 n값이 이미 소수인지를 판별한다.

-> 소수가 아닌경우 이미 앞에서 배수를 돌면서 i의 배수 또한 0이 되기 때문에 배수를 탐색할 필요가 없다.

* i가 배열의 범위나 자료형의 범위를 넘지 않도록 주의한다.

int prime[1001];
 
void checkprime()
{
    int i, j;
 
    for (i = 2; i < 1001; i++) {
        prime[i] = 1;
    }
 
    for (i = 2; i * i < 1001; i++) {
        for (j = i; prime[i] && i * j < 1001; j++)
            prime[i * j] = 0;
    }
}

소수 관련 문제

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

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

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