백준 1929 소수구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 원래 소수를 구하는 방식으로는 시간초과가 나서 에라토스테네스의 체 의 방식을 이용해야 시간초과 없이 문제를 해결 할 수 있었다.

 

 

package 수학2;
import java.io.*;
public class 소수_구하기 {
    public static boolean[] primeNum;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String [] in  =br.readLine().split(" ");
        int m = Integer.parseInt(in[0]);
        int n = Integer.parseInt(in[1]);
        primeNum = new boolean[n+1];
        getPrimeNum();
        for(int i=m;i<=n;i++){
            if(!primeNum[i]){
               sb.append(i).append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }
    private static void getPrimeNum() { //에라토스테네스의 체
        primeNum[1] = true;
        for(int i=2;i<primeNum.length;i++)
            for (int j = 2; i*j <primeNum.length ; j++) {
                primeNum[i*j] = true;
            }
    }
 
}
 

기존에 해결하려고 했던 방식

 

 

    static boolean chkPrime(int num){
        if(num <=1) return false;
        for (int i = 2; i < num ; i++) {
            if(num%i==0) return false;
        }
        return true;
    }