(JAVA)백준온라인 6588번 - 골드바흐의 추측

소수를 구하는 알고리즘을 사용하는 문제이다 !

//소수 판별하는 알고리즘
PrimeAry(){
        for(int i=2; i<=MAX; i++){
            isPrime[i] = true;
        }

        //소수 여부 판별
        for(int i = 2; i*i<=MAX; i++){
            if(isPrime[i]){
                for(int j= i*i; j<=MAX; j+=i){
                    isPrime[j] = false;
                }
            }
        }
    }

이 소수 판별 알고리즘은 먼저 isPrime배열(소수 판별)의 모든 요소를 true로 초기화 한 후, 제곱근 방식을 사용해서 소수에 해당되지 않는 각 index값을 false로 바꿔준다. 이를 이용하여서 이런 코드가 나온다

import java.util.Scanner;

public class Main {
    static int MAX = 1000000;
    static boolean[] isPrime = new boolean[MAX + 1];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        PrimeAry();
        while(true){
            int n = sc.nextInt();
            if(n == 0) break;

            boolean found = false;

            for(int i=2; i<=n/2; i++){
                //합의 경우가 여러개 나와도 자동으로 b-a가 큰것의 조합으로 나올 수 밖에 없음 i값이 작으면 n-i값이 크니까
                if(isPrime[i] && isPrime[n-i]){
                    sb.append(n).append(" = ").append(i).append(" + ").append(n-i).append("\n");
                    found = true;
                    break;
                }
            }
            if(!found){
                sb.append("Goldbach's conjecture is wrong.\n");
            }
        }
        System.out.println(sb.toString());

    }

    //결국 이게 젤 중요 소수를 판별하는 알고리즘이니깐
    static void PrimeAry(){
        for(int i=2; i<=MAX; i++){
            isPrime[i] = true;
        }

        //소수 여부 판별
        for(int i = 2; i*i<=MAX; i++){
            if(isPrime[i]){
                for(int j= i*i; j<=MAX; j+=i){
                    isPrime[j] = false;
                }
            }
        }
    }


}

나는 한참 실력이 모자라지만 이렇게 또 챗 GPT와 구글에서 많이 알아간다!