728x90
난이도 - 브론즈 2
문제
자연수 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을 출력한다.
728x90
에라토스테네스의 체를 사용한다. 2부터 n까지의 모든 수를 나열하고 2의 배수들을 모두 지운다. 남아있는 수 중에서 다음 수를 소수로 선택하고 그 수의 배수들을 모두 지운다. 이 과정을 범위의 끈까지 반복하고 남아있는 수들이 소수이다.
import java.io.*;
import java.util.Arrays;
public class Main2581 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int M = Integer.parseInt(br.readLine());
int N = Integer.parseInt(br.readLine());
boolean[] isPrime = sieveOfEratosthenes(N);
int firstPrime = -1;
int sum = 0;
for (int i = M; i <= N; i++) {
if (isPrime[i]) {
if (firstPrime == -1) {
firstPrime = i;
}
sum += i;
}
}
if (firstPrime == -1)
bw.write("-1");
else
bw.write(sum + "\n" + firstPrime);
bw.flush();
br.close();
bw.close();
}
static boolean[] sieveOfEratosthenes(int max) {
boolean[] isPrime = new boolean[max + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= max; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= max; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 11653번(소인수분해) (0) | 2024.06.23 |
---|---|
[백준 자바] 1929번(소수 구하기) - 에라토스테네스의 체 (0) | 2024.06.23 |
[백준 자바] 1978번(소수 찾기) (0) | 2024.06.22 |
[백준 자바] 1264번(모음의 개수) (0) | 2024.06.22 |
[백준 자바] 1312번(소수) (0) | 2024.06.22 |