1929) 소수 구하기 - Java

문제 )

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

1929번: 소수 구하기

 

 

 

풀이 )

에라토스테네스의 체를 이용하지 않아도 풀 수 있지만, (처음에는 그렇게 풀었음)
에라토스테네스의 체를 이용해서 푼 코드를 넣었다.

여기서 가장 신경을 썼던것은 21번째 줄에 있는 for문과 28번째 줄이다. 

primeNum[ i*j ] 로 한 이유는 맨처음 나오는 수는 소수이므로 true 값을 유지해야하기 때문이다.
j= 2, 3, 5, 7 .... 이 나올 때는 true  값을 줘야 나중에 소수구별이 가능하므로 i*j 라는 수식을 넣었다.

 

 

코드 )

import java.io.*;
import java.util.StringTokenizer;
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.valueOf(st.nextToken());
        int N = Integer.valueOf(st.nextToken());
        
        // default값이 false이므로 다른 수들에 따로 false 값을 넣지않아도 됨
        boolean[] primeNum = new boolean[N+1];
        
        // 2부터 N까지 모든 수에 true값을 넣음
        for(int i=2; i<=N; i++)
            primeNum[i] = true;
        
        for(int i=2; i<=N; i++) { // 2부터 N까지 전부 돌면서 검사
            for(int j=2; j*i<=N; j++) { // 소수가 아닌 수를 모두 false로 바꾸는 작업
                
                // 이미 검사가 되어 false 값이 들어갔다면 넘어감
                if( !primeNum[i*j]) continue;
                
                // 아직 검사가 안된값이라면 false 값을 넣음
                // ex). i=2, j=2 이면 i*j=4 의값이 false가 됨
                primeNum[i*j] = false;
            }
        }
        
        for(int i=M; i<=N; i++) { // M부터 N 사이의 소수를 찾음
            if( primeNum[i] == true ) bw.write(i+"\n");
        }
        br.close(); bw.flush(); bw.close();
    }
} cs