[알고리즘] 소수 (Prime Number)

mallin·2022년 2월 20일

algorithm

알고리즘

목록 보기

5/9

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

위 움짤처럼 1과 자기 자신만을 약수로 가지는 수를 소수라고 합니다.

예를 들어서 2 ~ 6 사이의 숫자가 있을 때에

숫자	약수	소수여부
2	1,2	O
3	1,3	O
4	1,2,4	X
5	1,5	O
6	1,2,3,6	X

2,3,5 는 1과 자기자신만을 약수로 가지고 있기 때문에 소수이고, 4와 6은 약수가 1과 자기 자신 뿐만 아니라 다른 수도 약수로 가지고 있기 때문에 소수가 아니게 됩니다.

소수 풀기 알고리즘

알고리즘 풀이 언어는 C++ 을 사용합니다. 이번엔 총 4가지의 푸는 알고리즘을 소개합니다.

① 2 ~ N-1 까지 돌면서 N 의 약수인지 확인

int n;
bool isPrimeNum = true;
cin >> n;

for (int i=2;i<n;i++) {
    if (n % i == 0) {
        isPrimeNum = false;
        break;
    }
}

cout << n << "은 소수" << (isPrimeNum ? "입니다.": "가 아닙니다.");

가장 간단한 방법으로 2부터 N-1 까지 돌면서 N 의 약수인지 확인합니다.

과정은 아래와 같습니다. 👇

1) 소수인지 아닌지 판단하기 위한 값인 N 을 입력받습니다.
2) 2 부터 N-1 까지 반복문을 돕니다.
3) 만약 N 을 해당 값으로 나눴을 때 나머지 값이 0 이라면 소수가 아니라고 판단합니다. 소수인지 판단하는 isPrimeNum 을 false 로 바꿔주고 반복문을 빠져나옵니다. (이미 소수가 아니라면 반복문을 더 돌 필요가 없기 때문에)

시간복잡도 는 O(N) 입니다.

② 2 ~ N/2 까지 돌면서 N 의 약수인지 확인

int n;
bool isPrimeNum = true;
cin >> n;

for (int i=2;i<=n/2;i++) {
    if (n % i == 0) {
        isPrimeNum = false;
        break;
    }
}

cout << n << "은 소수" << (isPrimeNum ? "입니다.": "가 아닙니다.");

1번과 로직은 동일하지만, 절반까지 값만 확인하는 방법입니다. 이렇게 해도 되는 이유는 N 의 절반 이상의 수는 비교해볼 필요가 없기 때문입니다. 만약 40 이라는 숫자가 있다고 가정했을 때 약수는 다음과 같습니다.

1,2,4,10,20,40

1x40, 2x20, 4x10 로 짝이 지어지기 때문에 2,4 로 나누어 떨어지는지만 확인하면 됩니다. 즉, 자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을 때 나머지가 0이 되는 숫자는 이미 이전에 나누었던 숫자일 수 밖에 없습니다.

해당 로직은 N/2 만큼 조회하지만 시간 복잡도에서 상수는 제외하기 때문에 시간복잡도는 O(N)이 됩니다.

③ 2 ~ 제곱근 까지 돌면서 N 의 약수인지 확인

int n;
bool primeNum = true;
cin >> n;

for (int i=2;i*i<=n;i++) {
    if (n % i == 0) {
        primeNum = false;
        break;
    }
}

cout << n << "은 소수" << (primeNum ? "입니다.": "가 아닙니다.");

이 방법도 2번과 동일하게 1번에서 반복문의 횟수만 줄이게 됩니다.
제곱근까지만 비교해도 되는 이유는 다음과 같습니다.
2번과 동일하게 40을 예시로 들 때 40의 약수는

1,2,4,10,20,40

입니다. √40 은 6.324555320.. 인데 약수를 짝을 지었을 때 곱하는 값 중 작은 값은 루트의 값보다 작을 수 밖에 없기 때문에 제곱근까지만 약수인지 확인해도 됩니다.

시간복잡도는 O(√N)이 됩니다.

④ 에라토스테네스의 체 사용

갑자기 에라토스네테스의 체 ? 뭔가 말이 되게 어려워 보이는데요.
어려워 보이는 이름에 비해 내용은 생각보다 간단합니다.

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부릅니다.

1~100 사이의 소수를 찾는다고 할 때 에라토스테네스의 체가 동작하는 방식은 다음과 같습니다.

1) 소수도 합성수도 아닌 유일한 자연수 1을 제거합니다.
2) 2를 제외한 2의 배수를 제거합니다.
3) 3을 제외한 3의 배수를 제거합니다.
4) 5를 제외한 5의 배수를 제거합니다. (4 같은 경우 2번째 과정에서 제거가 되었기 때문에 건너 뜁니다.
5) 7을 제외한 7의 배수를 제거합니다. (6 같은 경우 2번째, 3번째 과정에서 제거가 되었기 때문에 건너 뜁니다.)
6) 남은 수는 모두 소수 입니다.

👉 결론적으로 소수를 구해야 하는 범위의 제곱근 보다 작은 소수의 배수를 지우고 남은 수는 모두 소수 가 됩니다.

이중 for 문을 사용하는 방법과 for-while 문을 사용하는 방법 두 방식으로 풀 수 있습니다.

for-while 문 사용

int n;
cin >> n;

bool is_not_prime_number[n+1];
int j;

for (int i=2;i*i<=n;i++) {
    j = 2;

    while (i*j <= n) {
        is_not_prime_number[i*j] = true;
        j++;
    }
}

cout << n << "은 소수" << (is_not_prime_number[n] ? "가 아닙니다.": "입니다.");

에라토스테네스의 체는 일단 범위내에 있는 모든 소수가 아닌 값을 체크합니다.

과정은 다음과 같습니다.
1) is_not_prime_number 이라는 배열에 소수인지 아닌지를 저장합니다. true 인 경우 소수가 아니고, false 인 경우 소수입니다. c++ 에서 bool 초기값은 false 이기 때문에 초기값은 모두 false (소수) 로 들어가게 됩니다.

2) 3번 처럼 2~제곱근까지 반복문을 돕니다.

3) while 문을 통해 N 전까지의 값 중 i 의 배수를 is_not_prime_number 에 true 로 값을 넣어줍니다 (소수X)

4) is_not_prime_number 배열에서 N 이 true이면 소수가 아니고, false 인 경우 소수입니다.

이중 for 문 사용

int n;
cin >> n;

bool is_not_prime_number[n+1];

for (int i=2; i*i<=n; i++) {
    for(int j=i+i;j<=n;j+=i) {
        is_not_prime_number[j] = true;
    }
}

cout << n << "은 소수" << (is_not_prime_number[n] ? "가 아닙니다.": "입니다.");