[백준] 2581번 소수 (JAVA)

해결

• 입력값의 범위는 10000이하로, 대량의 범위에서 소수를 구해야 할 경우 알고리즘 ‘에라토스테네스의 체’를 이용하면 효율적으로 구할 수 있다.

  [참고]
  https://velog.io/@dayoung_sarah/알고리즘-에라토스테네의-체

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

		// N이하의 소수 여부 배열 구하기
        boolean[] primeArray = getPrimeArray(N);

		// 최솟값
        int min = -1;
		// 합
        int sum = 0;

		// M이상 N이하 소수 구하기
        for(int i=M; i< primeArray.length; i++) {
            if( !primeArray[i] ) {
                if( min == -1 ) {
                    min = i;
                }
                sum += i;
            }
        }

		// 소수가 없는 경우 -1 출력
        if( min == -1 ) {
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
    }

    public static boolean[] getPrimeArray(int max) {
        boolean[] primeArray = new boolean[max+1];
        primeArray[0] = true;
        primeArray[1] = true;

        for(int i=2; i <= Math.sqrt(max); i++) {
            if( primeArray[i] ) continue;

            for(int j=i*i; j<primeArray.length; j=j+i) {
                primeArray[j] = true;
            }
        }

        return primeArray;
    }
}