백준 1929 소수 구하기 자바

맨 처음에는 이렇게 하나하나 검토해서 나눠지는지 여부로 소수를 구했는데...

그러다보니 시간초과가 떠버렸다...!

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();

		for (int i = m; i <= n; i++) {
			boolean isPnum = true;
			if (i > 2) {
				for (int j = 2; j < i; j++) {
					if (i % j == 0) {
						isPnum = false;
						continue;
					}
				}
			}

			if (isPnum) {
				System.out.println(i);
			}
		}
    }
}

 

그래서 인터넷을 찾아보니...

배열을 이용하여 배수인 것들을 제외시켜서 남는 소수를 찾아내는 방법이 있었다!

그래서 다음처럼 풀었더니 정답이었다!ㅎㅎ

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();

		boolean[] isPrimeNum = new boolean[n + 1];// false일때 소수

		isPrimeNum[1] = true;// 숫자 1은 소수가 아님

		for (int i = 2; i <= n; i++) {
			for (int j = 2; j * i <= n; j++) {// 특정 숫자의 배수들은 소수가 아님
				isPrimeNum[i * j] = true;
			}
		}

		for (int k = m; k <= n; k++) {
			if (!isPrimeNum[k]) {// false인 것은 소수이므로 출력
				System.out.println(k);
			}
		}
    }
}

 

 

참조한 사이트 : https://pangsblog.tistory.com/39

[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)