[백준] 자바 Java, 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. 의식의 흐름대로 풀어본 풀이

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 백준 2581 문제] 소수
// 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램
public class Baekjoon2581 {
    public static boolean prime(int n) {
        if(n < 2) return false; // 1은 소수도 합성수도 아니다!

        // n을 2부터 n-1까지의 수로 n-1(1과 자기자신 제외) 나눴을 때 나머지가 0이면 합성수
        for(int i=2; i<n; i++) {
            if(n%i == 0) return false;
        }

        // 위의 조건문을 모두 통과시 소수이기 때문에 true 리턴
        return true;
    }

    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);

        int start = sc.nextInt(); // m부터
        int last = sc.nextInt(); // n까지
        int sum = 0;
        ArrayList<Integer> minArr = new ArrayList<Integer>();

        for(int i=start; i<=last; i++) {
            if(prime(i)) {
                sum += i;
                minArr.add(i);
            }
        }

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

    } //main end
}

2. "에라토스테네스의 체" 방법으로 풀어본 풀이

에라토스테네스의 체

• 에라토스테네스의 체
  • 소수(素數)를 찾는 방법
  • 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수

package level9_basic_math2;

import java.io.IOException;
import java.util.Scanner;

// 백준 2581 문제] 소수
// 자연수 M과 N이 주어질 때 M 이상 N 이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램
public class Baekjoon2581_EratosthenesSieve {
	// 에라토스테네스의 체 방법 사용
    public static void eratosthenes() {
        eratosArr[0] = true;
        eratosArr[1] = true;

        for(int i = 2; i <= Math.sqrt(eratosArr.length); i++) { // 구하려는 크기의 루트 값까지만 계산해도 모두 체크 가능!
            for(int j = i * i; j < eratosArr.length; j += i) {
                eratosArr[j] = true;
            }
        }
    }

    public static boolean eratosArr[];

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int start = sc.nextInt(); // m부터
        int last = sc.nextInt(); // n까지

        eratosArr = new boolean[last+1];
        eratosthenes();

        int sum = 0;
        int min = Integer.MAX_VALUE;

        for(int i=start; i<=last; i++) {
            if(eratosArr[i] == false) { // false == 소수
                sum += i;
                if(min == Integer.MAX_VALUE) { // 첫 번쨰 소수가 최솟값
                    min = i;
                }
            }
        }

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

    } //main end
}

 

• 최솟값 구하는 방법

[JAVA 문법] MIN_VALUE와 MAX_VALUE의 활용

 

결과