[BOJ]6588번: 골드바흐의 추측(java, c++)

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

6588번: 골드바흐의 추측

 

 

방법 1 : 숫자가 들어올 때마다 2개의 소수로 표현되는지 판정하기

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
 
        int num = 0;
        while((num = sc.nextInt()) != 0) {
            
            for (int i = 2; i < num; i++) {
                
                if(isPrimeNumber(i)) {
                    if (isPrimeNumber(num - i)) {
                        sb.append(num);
                        sb.append(" = ");
                        sb.append(i);
                        sb.append(" + ");
                        sb.append((num - i));
                        sb.append("\n");
                        
                        break;
                    }
                }
            }
        }
        
        System.out.println(sb.toString());
    }
 
    public static boolean isPrimeNumber(int num) {
 
        if (num < 2) {
            return false;
        }
 
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

 

방법 2 : max값 까지의 모든 소수를 저장한 배열을 만든 후, 들어온 수가 배열에 포함되는 소수들의 합으로 표현되는지 판정하기

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        int iMax = 1000000;
        boolean[] arrIsPrime = new boolean[iMax + 1];
        
        for (int i = 0; i < iMax; i++) {
            arrIsPrime[i] = isPrimeNumber(i);
        }
        
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
 
        int num = 0;
        while((num = sc.nextInt()) != 0) {
            
            boolean bGoldbachWasRight = false;
            
            for (int i = 2; i < num; i++) {
                
                if(arrIsPrime[i]) {
                    if (arrIsPrime[num - i]) {
                        sb.append(num);
                        sb.append(" = ");
                        sb.append(i);
                        sb.append(" + ");
                        sb.append((num - i));
                        sb.append("\n");
                        
                        bGoldbachWasRight = true;
                        break;
                    }
                }
                
                if(i == num -1 && !bGoldbachWasRight) {
                    sb.append("Goldbach's conjecture is wrong.");
                }
            }
        }
        
        System.out.println(sb.toString());
    }
 
    public static boolean isPrimeNumber(int num) {
 
        if (num < 2) {
            return false;
        }
 
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

c++소스

#include <iostream>
 
using namespace std;
 
const int MAX = 1000000;
bool isno_prime[MAX + 1];
 
void check_prime()
{
    for (int i = 2; i * i <= MAX; ++i)
    {
        if (isno_prime[i] == false)
        {
            for (int j = 2; i * j <= MAX; ++j)
            {
                isno_prime[i * j] = true;
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 에라토스테네스의 체 : 미리 MAX값까지 소수판정 해놓기
    check_prime();
 
    while (true)
    {
        int n;
        cin >> n;
        if (n == 0)
        {
            break;
        }
 
        bool possible = false;
        for (int i = 3; i < n; i += 2)
        {
            // 둘다 소수이면 출력
            if (!isno_prime[i] && !isno_prime[n - i])
            {
                cout << n << " = " << i << " + " << (n - i) << '\n';
                possible = true;
                break;
            }
        }
 
        if (!possible)
        {
            cout << "Goldbach's conjecture is wrong." << '\n';
        }
    }
 
    return 0;
}

 

 

골드바흐의 추측 Goldbach's conjecture

2보다 큰 모든 짝수는 두 소수의 합으로 표현가능하다. 10의 18승 이하에서 참인 것으로 증명되었다. 

 

약한 골드바흐의 추측 Goldbach's weak conjecture

5보다 큰 모든 홀수는 세 소수의 합으로 표현가능하다. 10의 27승 이하에서 참인 것으로 증명되었다.

 

 

 

TIP

문제의 최댓값이 10의 6승이므로, 가정이 틀렸을 때를 위한 예외처리를 해주지 않아도 되긴 했다 

 

방법 1 : 숫자가 들어올 때마다 2개의 소수로 표현되는지 판정하기

방법 2 : max값 까지의 모든 소수를 저장한 배열을 만든 후, 들어온 수가 배열에 포함되는 소수들의 합으로 표현되는지 판정하기

 

2가지 방법으로 풀어보았는데, 방법1이 더 메모리도 적게 잡아먹고 빨랐다.