[알고리즘] 백준 골드바흐의 추측 6588번 JAVA

2021/01/05 - [코딩/알고리즘] - [알고리즘] 백준 소수찾기 1978번 JAVA

[알고리즘] 백준 소수찾기 1978번 JAVA

 

시간 초과 뜸..

아무래도 primeNumber에서 반복횟수가 늘어나는 것 같다.

 

 

import java.util.Scanner;

public class Main_6588 {
    static int n=-1;//초기화
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int arry[] = new int[100000];
        int a=3,b;

        for(int i=0; n!=0; i++) {
            arry[i]=scanner.nextInt();
            if(arry[i]==0){
                n=i;
                break;
            }
        }


        for(int i=0; i<n; i++){
            b=arry[i]-a;
            while(true){
                if((primeNumber(a) == true && primeNumber(b) == true) ){
                    System.out.println(arry[i]+" = "+a+" + "+b);
                    break;
                }

                if(b-2>arry[i]/2) {
                    b-=2;
                    a=arry[i]-b;
                }
                else{
                    System.out.println("Goldbach's conjecture is wrong.");
                    break;
                }
            }
        }
    }
    
    public static boolean primeNumber(int a){
            int temp=a/2; // 나누는 수를 주어진 숫자/2 부터 시작
            while(temp!=0) {
                //나머지가 0인데 1로 나눴을 경우 소수이다.
                if(a%temp==0 && temp==1) return true;
                //나머지가 0인데 1이 아닐경우 소수가 아니기 때문에 다음수로 넘어간다.
                else if(a%temp==0) return false;
                temp--;
            }

            return false;
    }
}

 

primeNumber를 수정하고는 시간초과는 안떳는데 틀렸다고 나왔다..

 

문제는 a초기화가 제대로 안되었던 것이다.

 

for이 새로 시작하는 구문에서 백준에 나온 테스트케이스는 제대로 출력된다. 

마지막 42 = 5+37 로 나오기 때문에 

다음케이스의 a는 5로 시작하는 것

 

 

아래는 최종 답

 

변수 n은 사용하지 않아도 되어 삭제 하였다.

소수를 구하는 식은 검색하여 수정  

내가 사용한 방법은 시간복잡도가 n이고 

아래 방법은 루트n

import java.util.Scanner;

public class Main_6588 {
    static int n=-1;//초기화
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int arry[] = new int[100000];
        int a,b;
        
        for(int i=0; n!=0; i++) {
            arry[i]=scanner.nextInt();
            if(arry[i]==0){
                break;
            }
        }


        for(int i=0; arry[i]!=0; i++){
            a=3;
            b=arry[i]-a;
            while(true){
                if((primeNumber(a) == true && primeNumber(b) == true) ){
                    System.out.println(arry[i]+" = "+a+" + "+b);
                    break;
                }

                if(a+2<arry[i]/2) {
                    b-=2;
                    a=arry[i]-b;
                }
                else{
                    System.out.println("Goldbach's conjecture is wrong.");
                    break;
                }
            }
        }
    }
    
    public static boolean primeNumber(int num){
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
}