[java] 백준 알고리즘 2581번 소수 풀이

등차수열 공식을 이용해 시작하는 수(M)부터 끝나는 수(N)까지 총 합을 구하고,

소수가 아닌 수가 나올때마다 총 합에서 그 숫자를 빼주었다.

소수도 M과 N 사이의 숫자에서 소수가 아닌 값이 나올 때마다 빼주어

총 소수의 숫자를 구했다.

* 풀이 소스

public class Baekjoon2581{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        int primeNumSum = (N-M+1)*(M+N)/2; // M부터 N까지 합(등차수열 공식)
        int primeNumCount = N-M+1;
        int[] forFindingMin = new int[N-M+1];
        
        for(int i=M; i<=N; i++) {
            int primeNumber = i;
            int squareRoot  = (int) Math.sqrt(primeNumber);
            int divide = 2;
            
            if(primeNumber > 2) { // 나누는 건 2부터 나눠줘야 의미가 있어서 소수가 2 이상부터
                
                while(squareRoot >= divide) { // 나누는 부분은 나눠지는 수의 제곱근까지만 구해주면 된다.(수학공식)
                    
                    if(primeNumber%divide == 0) {
                        primeNumSum -= i;
                        primeNumCount--;
                        break;
                    }
                    
                    divide++;
                }
                
                if(primeNumber%divide != 0) {
                    forFindingMin[i-M] = primeNumber;
                }
            }else if(primeNumber == 1){ // 1이 입력될 경우 1을 빼줌(1은 소수가 아니니까)
                primeNumSum -= 1;
                primeNumCount -= 1;
            }else if(primeNumber ==2) {
                forFindingMin[i-M] = primeNumber;
            }
            
        }
        
        if(primeNumCount < 1) { // 소수가 하나도 없으면 -1 출력
            bw.write("-1");
        }else {
            bw.write(String.valueOf(primeNumSum));
            bw.newLine();
            for(int min : forFindingMin) {
                if(min != 0) { // int 배열은 디폴트가 0으로 채워져있기 때문에
                               // 0이 아닌 값이 나오는 첫순간이 최소값이다.
                    bw.write(String.valueOf(min));
                    break;
                }
            }
        }
        bw.flush();
        
    }
 
}