[Algorithm] 백준 6588 - 골드바흐의 추측 (JAVA)

[Algorithm] 백준 6588 - 골드바흐의 추측 (JAVA)

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

import java.util.ArrayList; import java.util.Scanner; public class Main { static ArrayList arr = new ArrayList<>(); static ArrayList chk = new ArrayList<>(); static int[] prime; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n; while (true){ n = sc.nextInt(); if (n == 0) break; arr.add(n); } prime = new int[100001]; isPrime(); for (int i = 0; i < arr.size(); i++) { dfs(arr.get(i), 0, 1); } } public static void dfs(int num, int start, int end) { int a = chk.get(start); int b = chk.get(end); if (a >= num/2) { System.out.println("Goldbach's conjecture is wrong."); return; } else if (a+b == num) { System.out.println(num + " = " + a + " + " + b); return; } else if (a+b > num) { dfs(num, start+1, start+2); } else { if (end == chk.size()-1) dfs(num,start+1, start+2); else dfs(num, start, end+1); } } public static void isPrime() { prime[0] = prime[1] = 1; for (int i = 2; i < prime.length; i++) { if (prime[i] == 0) { if (i % 2 == 1) chk.add(i); for (int j = i * 2; j < prime.length; j += i) { prime[j] = 1; } } } } }

stackoverflow, 시간 초과 오류 발생. 입력 값이 10만이다보니, 재귀를 피해야 한다.

import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { static ArrayList arr = new ArrayList<>(); static ArrayList chk = new ArrayList<>(); static int[] prime; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n; while (true){ n = sc.nextInt(); if (n == 0) break; arr.add(n); } int max = Collections.max(arr); prime = new int[max+1]; isPrime(); boolean key; for (int j=0; j

입력받은 개수 만큼 for문을 실행하며, n = a+b 구조이기 때문에 a가 n / 2일 때 까지 비교

a 번째와 n-a번째가 모두 소수이면 필터링하여 출력

사용 알고리즘 (에라토스테네스의 체 + a 번째 n-a 번째 소수판별)

from http://sasca37.tistory.com/123 by ccl(A) rewrite - 2021-12-18 16:02:11