6588번 '골드바흐의 추측'

import java.io.*;

import java.util.*;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

final int max = 1000000;

//6부터 1000000 까지의 소수 구해두기

int[] primes = new int[max];

int count = 0;

boolean[] isCleared = new boolean[max + 1];

for(int i=2; i<=max; ++i) {

if(!isCleared[i]) {

primes[count++] = i;

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

isCleared[j] = true;

}

}

}

int input = Integer.parseInt(in.readLine());

while(input != 0) {

if(input == 0) break;

for(int i=1; i<count; ++i) {

if(isCleared[input - primes[i]] == false) {

System.out.printf("%d = %d + %d\n", input, primes[i], input - primes[i]);

break;

}

}

input = Integer.parseInt(in.readLine());

}

}

}

일단 에라토스테네스의 체 알고리즘을 사용하여 소수를 쫙 구해놓는다.

그 다음 주어진 수에 대하여 1부터 탐색하여 소수의 합으로 표현되는지 찾아야 한다.

let max = 1000000

var primes = [Int]()

var isCleared = Array(repeating: false, count: max + 1)

for i in 2...max {

    if !isCleared[i] {

        primes.append(i)

        for j in stride(from: i * 2, through: max, by: i) {

            isCleared[j] = true

        }

    }

}

var input = Int(readLine()!)!

let count = primes.count

while input != 0 {

    if input == 0 { break }

    for i in 1..<count {

        if !isCleared[input - primes[i]] {

            print("\(input) = \(primes[i]) + \(input - primes[i])")

            break

        }

    }

    input = Int(readLine()!)!

}