글 읽기 - 왜 시간초과가 나오는지요..

sms2358 1년 전 0

잘 모르겠습니다 다른 방법이 있을까요?

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

public class Main {
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		
		
		for(int i=m;i<=n;i++) {
			int a = 0;
			if(m < 2) {
				continue;
			}
			else {
				for(int j=2;j<i;j++) {
					if(i % j == 0) {
						a++;
					}
				}
			}
			if(a == 0) {
				bw.write(Integer.toString(i) + "\n");
			}
		}
		bw.flush();
	}
}

mckkk119 1년 전 0

에라토스테네스의 체

에 대해서 검색해보시면 좋을 것 같습니다.

hinsung99 1년 전 3

이 방식으로 하면 M-N회의 반복문에서 각 (M <= K <= N)인 K회 만큼 시행하므로, 시간복잡도가 O(n²) 기 때문에 매우 비효율적인 코드가 됩니다.

1.소수의 배수는 전부 소수가 아니라는 점 (소수의 배수 =해당 소수를 약수로 가지고 있으므로 1과 자기 자신 외에 약수가 있음)

2.a를 굳이 더할 필요 없이 0보다 크기만 한다면 1과 자기 자신 외에 약수가 존재한다는 의미이므로 그 수는 소수가 아니라는 점

이 두 가지를 이용해서 계산 횟수를 줄일 수 있는 방법에 접근하면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

왜 시간초과가 나오는지요..

sms2358 1년 전 0

mckkk119 1년 전 0

hinsung99 1년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말