글 읽기 - 4948번 베르트랑 공준 JAVA 시간초과 관련

mss4236 5년 전 0

에라토스테네스의 체를 이용하여 코딩을 하였습니다.. 그런데 시간초과가 떠서 여기서 어떻게해야 시간을 더 줄일 수 있을지에 관련하여 질문드립니다.. 도와주세요 ㅠㅠ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		ArrayList<Integer> arr = new ArrayList<>();
		int testCase=1, num=0;

		try {
			while(true){
				testCase = Integer.parseInt(br.readLine());
				if(testCase == 0) break;
				else if(testCase != 0){
					num = testCase;
				}

				// 범위의 수를 arraylist에 저장
				for(int j=num+1; j<2*num+1; j++){
					arr.add(j);
				}

				// 소수가 아닌 수는 전부 지움
				for(int k=0; k<Math.sqrt(2*num+1); k++){
					for(int i=0; i<arr.size(); i++){
						if(k+2<num){
							if(arr.get(i)%(k+2)==0){
								arr.remove(i);
								i--;
							} else if(k+2>=num){
								if(arr.get(i)%(k+2)==0){
									if((k+2)==arr.get(i)){
										continue;
									} else{
										arr.remove(i);
										i--;
									}
								}
							} 
						}
					}
				}

				bw.write(String.valueOf(arr.size()));
				bw.newLine();
				arr.clear();
			}

			bw.flush();
			bw.close();
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

indioindio 5년 전 0

소수를 구하는 과정을 한번만 하고 저장하여 이용하는 것이 더 빠를 것 같네요.

mss4236 5년 전 0

소수를 구하는 과정을 따로 하나를 만들어서 거기서 구한거를 쓴다는 말인가요???

indioindio 5년 전 1

넵

mss4236 5년 전 0

맨 처음에 최대 범위만큼 소수를 판별해서 넣는 반복문을 이용해 배열을 만들고 주어진 범위를 이용해 count를 세서 하니깐 시간초과가 해결됐습니다 감사합니다

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

문제

문제

출처

ICPC

4948번 베르트랑 공준 JAVA 시간초과 관련

mss4236 5년 전 0

indioindio 5년 전 0

mss4236 5년 전 0

indioindio 5년 전 1

mss4236 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말