[백준] 1929번 : 소수 구하기 (java)

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

어떻게 생각하고 문제를 풀었는가?

소수가 아닌 수는 소수로 나누어 떨어져야 합니다.

따라서 2부터 시작하여 소수를 찾고, 해당 값의 곱으로 나타내어지는 수들을 소수가 아닌 수라고 결정할 수 있으므로 이를 구현한다면 문제를 해결할 수 있을 것이라고 생각하였습니다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int M = Integer.parseInt(tokenizer.nextToken());
        int N = Integer.parseInt(tokenizer.nextToken());
        reader.close();
        boolean[] primes = new boolean[N+1];
        Arrays.fill(primes,true);
        primes[1] = false;

        for(int i=2; i*i<=N; i++){
            if(primes[i]){
                for(int j= i*i; j<=N; j+=i){
                    primes[j] = false;
                }
            }
        }

        for(int i=M; i<=N; i++){
            if(primes[i]){
                System.out.println(i);
            }
        }
    }

}

 

N개의 숫자가 소수인지 아닌지 확인할 수 있도록 boolean 배열로 정의하였습니다.

모든 숫자를 소수라고 가정하고, 2부터 시작하여 해당 소수의 배수에 해당하는 index의 boolean 값을 false로 바꿈으로써 N개의 숫자들 중 소수인 숫자들을 확인할 수 있습니다.