[백준 알고리즘 JAVA] 2581번 소수

https://www.acmicpc.net/problem/2581

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을 출력한다.

 

 

핵심

1. scanner를 통해 정수 M과 N을 입력받고, M부터 N까지의 소수의 합을 담을 sum과 최솟값을 담을 min를 선언 및 초기화한다.

2. 정수의 약수의 개수를 담을 howMany를 선언 및 초기화하고, i 에서 j를 나눈 나머지가 0이면 howMany를 1씩 증가시킨다.

3. 소수는 1과 자기자신이 약수이므로 항상 약수가 2개이다. howMany가 2개이면 소수이기 때문에 sum에 누적해서 더해주고, 최솟값이 0이면 최초로 약수인 수가 min에 들어간다.

4. sum이 0이면 어떤 소수도 없기때문에 -1을 출력한다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int M = scanner.nextInt();
        int N = scanner.nextInt();

        int sum = 0;
        int min = 0;

        for (int i = M; i <= N; i++) {
            int howMany = 0;
            for (int j = 1; j <= i; j++) {
                if(i % j == 0){
                    howMany++;
                }
            }

            if(howMany == 2){
                sum += i;
                if(min == 0){
                    min = i;
                }
            }
        }
        if(sum == 0){
            System.out.println(-1);
        }else{
            System.out.println(sum);
            System.out.println(min);
        }
    }
}