백준 2581번 소수 (JAVA)

📌문제

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

예제 입력 

60
100

예제 출력 

620
61

 

 

 

에라토스테네스의 체를 이용하여 소수 구하기

📌답

import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        int m = readInt();
        int n = readInt();
        int ans =0;
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime,true);
        isPrime[0]=false;
        isPrime[1]=false;
        for(int i=2; i<Math.sqrt(n); i++) {
            for(int j = 2; j*i<=n; j++) {
                isPrime[i*j]=false;
            }
        }
        int min = 10001;

        for(int i=m; i<=n; i++) {
            if(isPrime[i]) {
                ans+=i;
                if(min>i) min=i;
          }
        }
        System.out.println(ans == 0 ? -1 : ans + "\n" + min);
    }
    private static int readInt() throws IOException {
        int n = 0;
        boolean isNegative = false;

        while (true) {
            int k = System.in.read();
            if (k <= 32) return isNegative ? n * (-1) : n;
            else if (k == '-') isNegative = true;
            else n = (n << 3) + (n << 1) + (k - '0');
        }
    }
}

 

 

 

 

 

 

 

끝까지 읽어주셔서 감사합니다 :)

Have a good day🐱

 

---

📢

1. 개발자 준비생이 공부한 내용을 정리한 글입니다. 내용에 오류가 있을 수 있습니다.
2. 위와 같은 이유로 내용에 대한 지적과 조언은 감사하게 받습니다.
3. 이 글의 내용은 계속 공부함으로써 언제든지 추가/수정 될 수 있습니다.