[알고리즘] 백준 1929번 소수 구하기 Java 자바

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.StringTokenizer;

public class Main {
    static List<Integer> primeNumberList;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer strToken=new StringTokenizer(br.readLine(), " ");
        int M=Integer.parseInt(strToken.nextToken());
        int N=Integer.parseInt(strToken.nextToken());
        primeNumberList =new ArrayList<Integer>();
        sb=new StringBuilder();
        primeNumberList.add(2);
        primeNumberList.add(3);

        primeNumberAdd(N);
        printResult(M,N);

    }

    //소수리스트에 추가
    public static void primeNumberAdd(int number){
        for(int i=5;i<=number;i+=2){
            isDivided(i);
        }
    }

    //소수로 나누었을때 떨어지는지 확인
    public static void isDivided(int number){
        int x=(int)Math.sqrt(number);
        for (Integer primeNumber:primeNumberList) {
            if(primeNumber>x){
                primeNumberList.add(number);
                return;
            }
            if(number%primeNumber==0) return; //나누어떨어지면 소수가 아님
        }
    }

    //결과를 출력
    public static void printResult(int M,int N){
        for (Integer primeNumber:primeNumberList) {
            if(M<=primeNumber&&N>=primeNumber) sb.append(primeNumber+"\n");
        }
        System.out.println(sb);
    }
}

문제풀이 : 소수란 1과 자신으로만 나누어떨어지는 정수

제곱근 범위 나누기 법으로 소수를 구해봤습니다.

제곱근(sqrt) 범위 나누기법이란? 
소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다는 방법으로 검사할 데이터를 제곱근 개 이하로 줄 일 수 있는 방법입니다.