[백준 1929] 소수 구하기 (JAVA)

백준 1929번 문제  - 소수 구하기

1929번: 소수 구하기

---

문제 분석

 

 

• 입력받은 범위의 숫자 중에 소수만 출력

 

---

해결 키 포인트

 

• 정수론: 소수구하기 - 에라토스테네스의 체의 원리

---

에라토스테네스의 체의 원리

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. ( 1도 소수가 아니다 ) 

 

에라토스테네스의 체 원리 알고리즘

 

1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성

2. 2부터 시작해 N의 제곱근까지 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다

3. 2~N의 제곱근 까지 탐색을 반복한 후 배열에서 남아있는 모든 수를 출력

 

N의 제곱근까지만 탐색하는 이유

N이 a*b라고 가정했을 때, a와 b 모두 N의 제곱근보다 클 수 없다. 따라서 N의 제곱근까지만 확인해도 전체 범위의 소수를 판별할 수 있다. 
만약 16의 범위까지 소수를 구할 때 16 = 4*4로 이뤄지면 16보다 작은 숫자는 항상 4보다 작은 약수를 갖게된다는 뜻
따라서 4까지만 확인하고 소수 판별을 진행하면 된다.

---

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static ArrayList<Integer> nums = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);

        // M, N 입력
        int M = sc.nextInt();
        int N = sc.nextInt();

        // 0 이상 N 이하 배열 제작
        for(int i=0;i<=N;i++){
            nums.add(i);
        }

        // 2부터 N까지 확인
        for(int i=2;i<=N;i++) {
            // 해당 값이 0이 아닐 때 출력 ( 0이면 소수가 아니라 제거된 값 )
            if (nums.get(i) != 0) {
                distinction(i, M, N);
            }
        }

        // 2부터 N까지 확인
        for(int i=M;i<=N;i++) {
            //해당 값이 1보다 클 때 출력 ( 0이면 소수가 아니라 제거된 값 )
            if (nums.get(i) > 1) {
                bw.write(nums.get(i) + "\n");
            }
        }

        bw.flush();
        bw.close();
    }

    public static void distinction(int i, int start, int end) {
        int mult = 2;
        for (int j = i*mult; j <= end; mult++, j = i*mult) {
            // 해당 값이 i로 나누어 떨어질 때 해당 값 소수에서 제거
            if (j >= start && nums.get(j) % i == 0) {
                nums.set(j, 0);
            }
        }
    }
}