글 읽기 - 자바 질문입니당~~ 도와주세요 ㅠㅠ 시간초과에요 문제쉬어용!

na1st 7년 전 0

시간초과 계속나와열!흑흑.. 자바의 길은 험난해요 ㅠㅠ

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException{

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		boolean flag = false;
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for(int i=a ; i<=b  ; i++){
			flag = false;
			for(int j=2 ; j<i;j++){
				if(i%j==0){
					flag = true;
				}
			}
			if(flag==false){
				if(String.valueOf(i).equals("1")==false)
				bw.write(String.valueOf(i)+"\n");
			}
		}
		bw.close();
	}
}

gallopsys 7년 전 0

지금 소수 구하는 알고리즘이 대략 O(n²)의 시간복잡도가 나옵니다. 최악의 경우 대략 10¹²초 정도로 대략 10⁹번의 루프에 1초가 소요된다고 하면, 1000초, 즉, 분 단위까지 소요될 수 있습니다.

이를 해결하기 위해 한 번 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해서 구해보세요.

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

문제

문제

출처

ICPC

자바 질문입니당~~ 도와주세요 ㅠㅠ 시간초과에요 문제쉬어용!

na1st 7년 전 0

gallopsys 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말