글 읽기 - 시간초과에 관련된 질문입니다.

wootool 3년 전 0

에라토스테네스의 체도 이용해서 25% 에서 50%로 많이 줄였지만 시간초과가 뜨네요

어디를 줄여야 할 지 모르겠습니다.

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {   	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
        // 입력
        
    	int a;
    	int num = 0;
    	String str = "";
    	do{
	    	String str_1 = br.readLine();
	    	int n = Integer.parseInt(str_1);
	    	a = n;
	    	if(a != 0) {
	    		str = str + str_1  + "/"; 
	    		num++;
	    	}
	
    	}while(a != 0);
	    
    	String[] STR = str.split("/");
    	int[] NUM = new int[num];
    	
        // 입력한 data를 정리
        
    	for(int i = 0; i < num; i++) {
    		 		
    		NUM[i] = Integer.parseInt(STR[i]); 
    		
    		int[] pri_0 = new int[(int)NUM[i] + 1];
    		   
            // 에라스토스테네스의 체 이용
    		for(int j = 0; j <= NUM[i]; j++){ 
    			if (j < 2) {
    				pri_0[j] = 0;
    			}
    			else {
    				pri_0[j] = j;
    			}
    		}
    		
    		for(int j = 2; j <= NUM[i]; j++){
        		if (pri_0[j] == 0) {
        			continue;
        		}
        		for(int k = 2 * j; k <= NUM[i]; k += j) {
        			pri_0[k] = 0;
        		}
    		}    		
    	  	
            // 에라스토스테네스의 체로 거른 것으로 골드바흐의 추측을 할 수 있는지 추정
    		boolean chk = false;
    	
    		for(int j = 0; j <= NUM[i]; j++) {
        		if (pri_0[j] == 0) {
        			continue;
        		}
    			
    			if(chk == true){
    				break;
    			}
    			for(int k = NUM[i] - 1; k >= 0 ; k--){
            		if (pri_0[k] == 0) {
            			continue;
            		}
    				if (pri_0[j] + pri_0[k] < NUM[i] || pri_0[j] == pri_0[k]) {
    					break;
    				}
    				else {
        				if (pri_0[j] + pri_0[k] == NUM[i]) {
        					System.out.println(NUM[i] + " = " + pri_0[j] + " + " + pri_0[k]);
        					chk = true;
        					break;
        				}
    					
    				}

    			}

    		}
    		
    		if(chk == false){
    			System.out.println("\"" + "Goldbach's conjecture is wrong." + "\"");
    		}   
    	
        }
        
    }	
    
}

wogus23 3년 전 0

제가 자바를 잘 몰라서 정확하지는 않지만 47번째줄에 에라토스 체 만들 때 수의 범위 전체를 돌리지말고 제곱 근 까지만 돌리셔도 됩니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과에 관련된 질문입니다.

wootool 3년 전 0

에라토스테네스의 체도 이용해서 25% 에서 50%로 많이 줄였지만 시간초과가 뜨네요

어디를 줄여야 할 지 모르겠습니다.

wogus23 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말