[알고리즘] 특정 숫자가 소수인지 알고 싶을 때

특정 숫자가 소수인지 알고 싶을 때

1. 그냥 반복문 돌리기

A라는 숫자가 소수인지 알고 싶으면, 단순하게 생각했을 땐 그냥 반복문을 돌리면 된다.

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

...
if (isPrime(N)) {
	// 소수
}
else {
	// 소수 X
}
...

N 의 값이 작다면 그냥 이렇게 해도 되긴 하다 !

---

🚨 문제: 입력값이 엄청나게 큰 경우에는?

하지만 BOJ 4134 처럼 입력값이 어마어마하게 크다면 !?

비효율적일 뿐더러 알고리즘 문제에서는 시간 초과가 날 것이다
그래서 2번 방법을 쓰면 보다 효율적으로 소수 판별을 할 수 있다 ! !

---

2. √N 까지만 나눠보기

이 방법도 반복문을 돌린다는 점에서는 1번과 똑같지만,
1번 방법은 N-1까지 반복문을 돌리지만, 2번 방법은 √N까지만 돌린다는 점에서 차이가 있다.

❔ 왜 √N까지만 돌려도 되냐면 ..

100을 예로 한 번 들어보자.

1 * 100
2 * 50
4 * 25
5 * 20
10 * 10
20 * 5
25 * 4
50 * 2
100 * 1

이렇게 100을 두 수의 곱으로 나타내면, 10 * 10 을 기준으로 대칭임을 알 수 있다.
그렇기 때문에 10 ( = √100 ) 까지만 확인하면 되고,

결론적으로, √N까지만 확인해주면 소수인지 아닌지를 알 수 있다는 것이다.

코드

그래서 다음과 같이 코드를 작성하면 된다.
M부터 N까지의 소수를 모두 출력하는 코드이다.

[Ex] BOJ 4134

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 입력
    int M, N;
    cin >> M >> N;
    
    // 연산 및 출력
    for (int i=M; i<=N; i++) {
        if (i == 1)
            continue;
        else {
            if (isPrime(i))
                cout << i << "\n";
        }
    }
    
    return 0;
}

---

3. 에라토스테네스의 체

이 방법도 소수를 찾는 방법인데, O(N^1/2)의 시간복잡도를 가져 대량의 소수들을 구해야 할 때 아주 유용하다.

에라토스테네스의 체는 "1을 제외한 수의 배수가 되는 수는 소수가 아니다." 라는 소수의 개념을 이용한 알고리즘으로,
임의의 수 n까지의 소수를 구하고자 할 때, √N까지의 모든 배수들을 소수에서 제외시키는 방식이다.

❔ 예를 들어 보자면 ..

N=150 일 때, 2부터 N까지의 모든 소수를 구해보자고 하자.
bool 타입의 배열을 선언하고 false 로 초기화를 한다.
그리고 2부터 √N까지 반복문을 돌리면,

1. i = 2: 2 == 소수 -> num <= N인 모든 num에 대해서, 2의 배수들을 true 표시
2. i = 3: 3 == 소수 -> num <= N인 모든 num에 대해서, 3의 배수들을 모두 true 표시
3. i = 4: 4 != 소수 -> i = 2일 때 true 표시 되었으므로 pass
4. 이 과정을 √N까지 반복한다.

코드

코드는 다음과 같이 작성하면 된다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 할 때,
짝수 N의 골드바흐 파티션의 개수를 구하는 문제이다.

[Ex] BOJ 17103

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAX_NUM = 1000001;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 입력
    int T, input, cnt;
    cin >> T;
    
    // 먼저 채워놓기
    // 여기가 에라토스테네스의 체
    vector<bool> primes(MAX_NUM, false);
    for (int i=2; i<=sqrt(MAX_NUM); i++) {
        // 이미 true -> pass
        if (primes[i])
            continue;
        // 배수 체크해주기
        for (int j=2*i; j<=MAX_NUM; j+=i)
            primes[j] = true;
    }
    
    // 연산 및 출력
    while (T--) {
        cin >> input;
        
        // 개수 초기화
        cnt = 0; 
        
        // 대칭 -> 반만 검사
        for (int i=2; i<=input/2; i++) {
            // 소수 아님 -> pass
            if (primes[i]) 
                continue;
            
            // 나머지도 소수
            if (!primes[input-i])
                cnt++;
        }
        
        cout << cnt << "\n";
    }
    
    return 0;
}

+) 추가로 ..

참고로 1은 소수가 아니다 !!!!!!
맨날 헷갈림 ㅋ

---

참고

https://bbty97.tistory.com/17
https://forward-movement.tistory.com/98