반응형

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public void solution() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Boolean[] booleans = new Boolean[1000001]; Arrays.fill(booleans, false); booleans[0] = booleans[1] = true; for(int i=2; i<Math.sqrt(booleans.length); i++){ if(booleans[i]) continue; for(int j=i*i; j<booleans.length; j+=i){ booleans[j] = true; } } int number = 0; while((number = Integer.parseInt(br.readLine()))!=0){ boolean check = false; for(int i=2; i<=number/2; i++){ if(!booleans[i]&&!booleans[number-i]){ System.out.println(number + " = " + i + " + " + (number-i)); check = true; break; } } if(!check){ System.out.println("Goldbach's conjecture is wrong."); } } } public static void main(String args[]) throws IOException { new Main().solution(); } }
이 문제 역시 에라토스테네스의 체를 이용한다. 주어진 범위만큼 배열에 소수를 초기화 해놓고, 값을 입력 받아서 대칭이라는 점을 활용해 입력 받은 n/2 까지 for문을 돌려서 Array[i] 가 소수이고, Array[n-i] 가 소수 일때 출력하고 break문으로 빠져나온다. 그때 짝수를 두 홀수의 합으로 나타낼 수 없는지 체크하는 boolean 값을 설정해주고, 나타낼 수 없을때 출력해준다.
반응형
'개발 > 알고리즘' 카테고리의 다른 글
백준 3085번 : 사탕 게임 (0) | 2022.12.29 |
---|---|
백준 2309번 : 일곱 난쟁이 (0) | 2022.12.28 |
백준 1929번 : 소수 구하기 (0) | 2022.12.28 |
백준 1978번 : 소수 찾기 (0) | 2022.12.27 |
백준 17425번 : 약수의 합 (0) | 2022.12.25 |