1929. 소수구하기 (자바, Java)

범위가 엄청 커졌다. 시간복잡도가 O(n^2)인 방법으로는 통과하기 어렵습니다. (시간초과)

이전에 배운 에라토스테네스의 체를 이용하면, 큰 문제없이 풀 수 있습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		boolean[] prime = new boolean[n+1]; // false면 소수, true면 소수아님

		for (int i=0; i<=Math.sqrt(n); i++) {

			if (i<2) {

				prime[i] = true;
				continue;

			}

			if (prime[i] == true) {

				continue;

			}


			for (int j=i*i; j<prime.length; j+=i) {

				prime[j] = true;

			}



		}

			for (int i=m; i<prime.length; i++) {

				if (prime[i] == false) {

					System.out.println(i);

				}

			}
	}

}