2581번 소수

https://www.acmicpc.net/problem/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을 출력한다.

풀이

주어진 영역내의 소수의 합과 최소값을 구해야 하므로

에라토스테네스의 체를 활용하였다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

해당 공식은 소수인 2 부터 시작하여 2의 배수를 모두 지우고, 이 다음 소수인 3의 배수를 모두 지우고...

이를 활용하면 주어진 범위내의 모든 소수를 쉽게 찾을수 있다.

1. 정수 m과 n을 입력받고 boolean 타입의 배열을 n+1 크기로 생성한다.
2. 반복문을 2부터 시작하여 배열의 값이 false인  경우 해당 값의 배수를 모두 true로 바꾼다.
3. 이렇게 하면 모든 소수는 false로 배열에 저장된다.
4. 나머지 0과 1은 따로 false 처리 한다.
5. m ~ n 범위의 배열중에서 값이 false인 배열을 찾는다.
6. 만약 sum이 0이라면 (첫번째 값이라면) 최소값이므로 저장한다.
7. sum에 모든 소수를 더해준다.
8. 최종적으로 sum이 0이라면 소수가 없는것이므로 -1을 출력하고 그외에는 sum과 최소값을  출력한다.

아래는 이를 구현한 코드이다.

// 에라토스테네스의 체
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();

        int min = 0;
        int sum = 0;

        boolean[] arr = new boolean[n+1];

        for (int i = 2; i < n+1; i++) {
            if (!arr[i]) {
                for (int j = i+i; j < n+1; j+=i) {
                    arr[j] = true;
                }
            }
        }

        arr[0] = true;
        arr[1] = true;

        for (int i = m; i < n+1; i++) {
            if (!arr[i]) {
                if(sum == 0) min = i;
                sum += i;
            }
        }

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

    }
}

 

이번 문제를 풀면서 몇번씩 쓰고 지우고를 반복했다.

뭔가 잘못된것 같으면 모두 주석처리하거나 다 지워버리고 처음부터 다시 생각하는게 도움이 되는 것 같다.