백준 2581번 자바 소수 [기본 수학2] 에라토스테네스의 체

 

간단하다. m, n 두 수를 입력 후 m과 n 사이의 소수의 합을 출력하고 가장 작은 소수를 출력하면 된다.

여기서는 에라토스테네스 체 방법을 이용해서 문제를 풀어본다.

import java.util.Scanner;
 
public class Main {
    //baekjoon 2581 소수 수학2
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        boolean arr[] = new boolean[n+1]; //최대치 만큼 배열 할당
        
        arr[0] = true;
        arr[1] = true;
 
        for(int i=2; i<=Math.sqrt(n+1); i++) {
        //i의 제곱수 부터 검사하므로 i는 전체범위(n+1의 제곱근까지 검사한다.
            for(int j =i*i; j<n+1; j += i) { // i * i 처음에 4..6..8... 다음은 3의 배수부터 검사
                arr[j] = true;        //소수가 아닌수는 true
            }
        }
        
        int min = Integer.MAX_VALUE; //최솟값 변수
        int sum = 0;    
        for(int i = m; i<n+1; i++) {
            if(arr[i] == false) {
                if(min > i)
                    min = i; 
                sum += i;
            }
        }
        if(sum == 0)
            System.out.println(-1);
        else {
            System.out.println(sum);
            System.out.println(min);
        }
 
    }
 
}

소수 구하는 방법이야 여러가지 있지만 여기서는 에라토스테네스 체 라는 방법을 사용했다.

16행 : i는 2부터 검사할 지점의 수의 제곱근 까지 반복하고 (i를 제곱해서 사용할 것이기 때문)

18행 : j는 i의 제곱부터 검사할 범위 까지 반복하고 i만큼 증가시킨다.

(i의 배수는 소수가 아니므로 배수를 전부 체크한다.)

23행 : 최솟값 출력할 변수 선언 및 초기화

26행~29행 : bool 배열 arr[i] 가 false 면 i가 소수이므로 sum에 값을 더해주면 된다.

min최솟값도 저장해 준다.

 

에라토스테네스 방법은 소수를 찾을 때 범위가 지정되어 있는 경우 사용하기 좋은 알고리즘이다.

그럼20000