[백준] 6588번 : 골드바흐의 추측 with python3, java

12 Oct 2018

Reading time ~1 minute

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

import sys
read = lambda : sys.stdin.readline().strip()
m = 10**6+10
check = [True]*m
primes = []
check[0] = check[1] = False

i = 1
while i*i <= m:

    if check[i]:
        j = i+i
        while j < m:
            check[j]=False # 소수 x
            j +=i
        if i != 2:
          # i는 소수면서 2가 아닌거
            primes.append(i)
            # 어차피 위에 while문에서 i가 되기전에 소수 아닌것은 다 check했을 테니 이렇게 해도 된다.
    i += 1

while True:
    a = int(read())
    if a == 0: break
    for p in primes:
        if check[a-p] :
            print(a, "=", p, "+", a-p)
            break


import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    private static final int MAX = 1000000;
    private static final Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        boolean[] check = new boolean[MAX+1];
        ArrayList<Integer> primes = new ArrayList<Integer>();
        check[0] = check[1] = true;
        for (int i=2; i*i <= MAX; i++) {
            if (check[i] == true) {
                continue;
            }
            primes.add(i);
            for (int j=i+i; j<=MAX; j+=i) {
                check[j] = true;
            }
        }
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            for (int i=1; i<primes.size(); i++) {
                int p = primes.get(i);
                if (check[n - p] == false) {
                    System.out.println(n + " = " + p + " + " + (n-p));
                    break;
                }
            }
        }
    }
}