2581. 소수 [JAVA]

1978번 문제와 같이 주어진 숫자 범위 내에서 소수를 구하고, 그 범위내의 최소값인 소수와
소수들의 총 누적합을 구한다.

이번에는 다른 방법으로 풀이해보았다.
제곱근을 이용한 소수 판별 https://st-lab.tistory.com/80 참고

특정숫자 n이 a x b 일때, a 혹은 b 둘중 하나는 제곱근보다 같거나 작아야한다.
ex) 11의 경우 대략 3.32 가 제곱근이 므로,
3까지 11에 대해 소수인지를 체크하면 그 이상의 수에 대해선 소수 판별을 하지 않아도 된다.
제곱근 3.32 이상의 수들에 대해서는 1,2,3 들을 약수로가지는 수 혹은 소수뿐이므로 그 이상 알아보지 않아도된다.

따라서 아래와 같이 코드를 짜보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//소수
//2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 2
public class BJ_2581 {
    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());
        if(m < 0 || m > 10000) return; // 숫자 제한
        if(n < 0 || n > 10000) return; // 숫자 제한

        int primeSum = 0; //소수합
        int minPrimeNUm = -1;//최소값 소수

        outer : for(int i = m; i <= n; i++){
            int dividend = (int)Math.sqrt(i); // 제곱근 이상인 경우는 어차피 제곱근 이하인 수들에 대해 배수및 약수로 되기때문.

            while(dividend > 1){
                if(i % dividend-- == 0) continue outer; // 제수를 피제수로 나누면서 나머지 체크
            }

            if(dividend == 1 && i != 1) { //1까지 나누게된 수 및 제수가 1이아닌수
                if(minPrimeNUm == -1) minPrimeNUm = i; // 최소 소수가 할당되지 않았따면 할당
                primeSum += i; // 합계 누적
            }
        }
        if(minPrimeNUm == -1) {
            System.out.println(-1);
            return;
        }
        System.out.println(primeSum);
        System.out.println(minPrimeNUm);
        
    }
}

백준 2581 소수