Don't give up!

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

Coding Test/BOJ

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

Heang Lee 2021. 8. 8. 16:38

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

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

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

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

따라서 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개의 숫자들 중 소수인 숫자들을 확인할 수 있습니다.