[1978,1929,6588번] 소수 찾기, 에라토스테네스의 체, 골드바흐의 추측

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

1978번: 소수 찾기

소수는 약수를 1과 자기 자신만 갖는 수입니다.

하나의 소수를 찾는 방법은 간단한데요.

어떤 수 n이 소수인지 아닌지 판단하기 위해서는 2부터 n 직전의 수까지 전부 나누어보면서 한번이라도 나누어 떨어지게 되면 소수가 아니게 되죠. (어떤 수의 약수를 찾는 방법과 동일)

 

아래 코드의 prime 함수에서 for문의 조건문 i * i <= n 의 이유를 설명하자면,

어떤 수 n을 \(n = a * b\) (a ≤ b) 라고 해봅시다.

n을 두 수의 곱으로 나타낸다고 했을 때 a가 1일 경우는 제외하고 2라고 했을 때 b는 \(\frac{n}{2}\)가 될 것입니다.

즉, n직전의 수까지 굳이 나누어볼 필요가 없다는 것이에요.  \(\frac{n}{2}\)가 약수의 최대값이므로 \(\frac{n}{2}\)까지만 나누어보면 소수인지 아닌지 확신할 수 있기 때문이죠.

 

여기서 나아가서 a를 2부터 시작해서 쭉 나누어가다보면 a와 b가 같거나 커지는 순간이 올 것입니다.

그 때의 경계값을 알고 있다면 그 이후는 a로 계속 나누어 떨어지는지 아닌지를 확인해볼 필요가 없습니다.

a가 b보다 커지게 되면 \(n = a * b\)식을 만족해야하기 때문에 단지 a와 b를 바꿔 놓은 것에 불과합니다. 경계값 이전의 a가 지금은 b가 되는거지요.

즉 경계값을 구하기 위해서는 a와 b가 거의 비슷해야 할 것입니다.

두 수를 곱해서 n이 나올 때, a와 b의 차이가 거의 없도록 하는 값은 무엇일지 생각해보면 \(\sqrt{n}\) 이 됩니다.

 

예를 들면 29라는 수가 소수인지 아닌지 판단하기 위해서 29의 제곱근 \(\sqrt{29}=5.385⋯\) 까지 나누어보면 되겠지요.

약수는 무조건 정수이므로 5보다 같거나 작은 정수까지만 나누어 보면 됩니다.

2부터 5까지 나누어서 한번도 나누어 떨어지지 않는다면 소수가 됩니다.

 

코드에서의 i * i <= n 는 i <=\(\sqrt{n}\) 와 동일한 표현입니다.

\(\sqrt{n}\) 는 실수가 되어 근사값이 될 수 있기에 정수 연산으로 바꾸어 조건문을 표시하는 것이 좋습니다.

 

 

[코드]

#include <iostream>
using namespace std;
bool prime(int n) { //n이 소수 인지 아닌지 판단하는 함수. true일 경우 소수.
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main () {
    int n;
    cin >> n;
    int cnt = 0;
    int input;
    while (n--) {
        cin >> input;
        if(prime(input)) cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

[결과]

4
1 3 5 7
3

 

 

 

 

 

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

1929번: 소수 구하기

이 문제는 M이상 N이하의 소수를 모두 찾아야 하는데 M과 N의 제한이 1 ≤ M ≤ N ≤ 1,000,000 입니다.

이렇게 범위의 소수를 전부 찾아야 하고 수가 클 때는 에라토스테네스의 체를 이용하면 쉽게 구할 수 있습니다.

 

2부터 N까지의 수들을 나열해놓고 아직 지워지지 않은 수 중에서 가장 작은 수가 소수가 됩니다.

즉, 맨 처음 시작은 2이므로 2는 소수입니다.

그러면 2의 배수들을 전부 지운 후 3으로 넘어가게 되고 3도 소수이므로 3의 배수를 전부 지워나가게 됩니다.

이를 계속 반복하면서 결국 최종적으로 지워지지 않고 남은 수들은 소수가 됩니다.

 

코드를 보면 두번째 for문에서 j=i*i 로 작성하는 것이 맞으나, i가 매우 큰 수라면 int 범위를 넘어설 수도 있기 때문에 i*2로 작성하는 것이 좋습니다.

 

[코드]

#include <iostream>
using namespace std;
bool check[1000001]; //지워졌으면 true
int main(){
    check[0] = check[1] = true; //0, 1은 지운다
    int m, n;
    cin >> m >> n;
    for (int i = 2; i * i <= n; i++) {
        if (check[i] == false) { //지워지지 않았다면 소수이므로
            for (int j = i * 2; j <= n; j += i) { //그 수의 배수를 전부 지운다
                check[j] = true;
            }    
        }
    }
    for (int i = m; i <= n; i++) { //m~n까지 지워지지 않은 수를 출력한다
        if(!check[i]) cout << i << '\n';
    }
    return 0;
}

[결과]

3 16
3
5
7
11
13

 

 

 

 

 

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

6588번: 골드바흐의 추측

골드바흐의 추측을 증명하라는 문제입니다. 

백만 이하의 모든 짝수에 대해 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있는 것을 증명하면 됩니다.

에라토스테네스의 체로 쉽게 구현할 수 있습니다.

먼저 위 문제에서와 같이 에라토스테네스의 체로 백만까지의 모든 소수들을 먼저 구해놓습니다.

 

그리고 입력값으로 주어지는 정수 n 은 반드시 짝수이며 범위가 6 ≤ n ≤ 1000000 입니다.

그래서 i를 3부터 n 미만까지 홀수로만 증가하도록 하였습니다. 그러면 n-i가 홀수라는 것이 이미 보장되기 때문에 n-i를 따로 홀수 체크 하지 않았습니다.

즉, i와 n-i가 소수이기만 하면 됩니다. 

 

[코드]

#include <iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];
int main () {
    check[0] = check[1] = true;
    for (int i = 2; i * i <= MAX; i++) {
        if (check[i] == false) {
            for (int j = i * 2; j <= MAX; j += i) {
                check[j] = true;
            }
        }
    }
    //매우 많은 입력이 주어질때 속도가 느려짐을 방지
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    int n;
    while(cin >> n) {
        bool flag = false;
        if (n == 0) break;
        for (int i = 3; i < n; i += 2) { //홀수만 체크해본다
            if (!check[i] && !check[n - i]) {
                cout << n << " = " << i << " + " << n - i << '\n';
                flag = true;
                break;
            }
        }
        if (!flag) cout << "Goldbach's conjecture is wrong." << '\n';
    }
    return 0;
}

[결과]

8 //input
8 = 3 + 5
20 //input
20 = 3 + 17
42 //input
42 = 5 + 37
0 //input