[Algorithm]에라토스테네스의 체 자바풀이 소수찾기 백준 1929번 문제

문제는 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하라네요.

먼저, 소수를 구하려면 에라토스테네스의 체를 알아야합니다.

소수를 구할 때 가장 많이 사용되는 방법입니다.

 

 

이미지 출저 - 위키백과

 

2의배수, 3의배수, 5의배수, 7의배수를 전부 걸러내면 소수만 남습니다.

마치 체에 걸러내고 만든사람이 고대 그리스의 에라토스테네스라는 사람이라서

이 알고리즘의 이름을 에라토스테네스의 체 라고 부릅니다.

 

 

결과값은 다음과 같이 나와야합니다.

 

그러면 에라토스테네스의 체를 이용한 소수구하기 백준 1929번문제 자바코드로 풀이해보겠습니다.

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] solution = solution(m, n);
        for (int i = m; i < n + 1; i++) {
            if (solution[i] == false) {
                System.out.println(i);
            }
        }

    }

    public static boolean [] solution(int m, int n) {

        boolean [] answer = new boolean[n + 1];

        answer[0] = true;
        answer[1] = true;

        for (int i = 2; i < Math.sqrt(n + 1); i++) {
            for (int j = i * i; j < n + 1; j = j + i) {
                answer[j] = true;
            }
        }


        return answer;

    }
}