백준/2581/소수/JAVA

2581번: 소수 (acmicpc.net)

2581번: 소수

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

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

public class Main {
	public static void main(String args[]) throws IOException{
	   	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   		
	   		int min = Integer.parseInt(br.readLine());
	   		int max = Integer.parseInt(br.readLine());
        
        int s =0;
        int n =0;
        int sum =0;
        int min_value =0;
        
        for(int i=min;i<=max;i++){ //작은수부터 큰수까지 반복문 돌리기
            if(i !=1){ //1은 예외처리
                for(int j=2;j<=(int)Math.sqrt(i);j++){ 
                    if(i%j ==0){ //소수가 아닌경우
                        s+=1;
                    }
                }
                if(s ==0){ //소수인경우 
                    sum +=i;
                    n+=1; //소수일경우에 변수n에 1을 추가한다.
                    if(n ==1) min_value = i; //처음 1을 추가할때의 min값이 소수의최솟값
                }
                s = 0;
                
            }
        }
        System.out.println(sum !=0 ? sum + "\n" + min_value : -1);
    }
}

Math.sqrt(i)를 이용해 i의 제곱근 이하의 숫자들 이하인경우의 숫자들까지 증가해가면서 한개씩 나누어 떨어지면 인수가 있기 때문에 소수가 아닌 경우다. 소수인경우에는 s ==0인 경우이므로 소수의 합을 구해야하므로 sum +=i를 해준다.

sum !=0인경우는 소수인경우이므로 sum값과 소수의 최솟값을 출력해주면 된다. 그리고 1은 예외이기 때문에 s=0이므로 sum =0이므로 -1을 출력해준다.