[백준] 1929번 : 소수 구하기 – JAVA [자바]

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

1929번: 소수 구하기

 

---

• 문제

 

 

---

• 문제 풀이

백준 1929번 소수 구하기는 실버 3 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 자연수 M과 N이 주어진다. 그리고 M 이상 N 이하의 소수들을 모두 출력해주면 되는 문제이다.

 

이 문제에서는 에라토스테네스의 체 알고리즘을 이용해서 풀 것이다. 에라토스테네스의 체를 잘 모르면 밑에 있는 글을 참고하면 되겠다.

 

https://propercoding.tistory.com/182

[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes)

 

우선 에라토스테네스의 체 원리처럼 크기가 n인 배열을 선언하고 m부터 n까지만 초기화해준다. 그리고 2부터 시작해서 n까지 for-loop을 돌리고 이 자연수들의 배수들을 모두 배열에서 지워준다. 이때 지워주는 것은 단순히 배열 값을 0으로 바꿔주면 된다. 

 

이러면 배열에는 자연수들의 배수를 모두 지웠으니 소수만 남게 된다. 이제 이 소수들을 StringBuilder를 이용해서 마지막에 한꺼번에 출력만 해주면 된다.

 

자세한 코드는 밑에 있는 코드를 참고하면 되겠다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        primeNumber(m, n);
    }
    
    //에라토스테네스의 체 이용
    static void primeNumber(int m, int n) {
        int[] arr = new int[n+1];
        StringBuilder sb = new StringBuilder();
        
        //배열 초기화
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
        
        //2부터 시작해서 i의 배수들을 배열에서 지워준다
        for (int i = 2; i <= n; i++) {
            //이미 지워진 수는 건너뛴다
            if (arr[i] == 0) continue;  
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }
        for (int i = m; i <= n; i++) {
            if (arr[i] != 0) sb.append(i + "\n");
        }
        System.out.print(sb);
    }
}