728x90
난이도 - 실버 2
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
728x90
에라토스테네스의 체를 사용한다. 2부터 n까지의 모든 수를 나열하고 2의 배수들을 모두 지운다. 남아있는 수 중에서 다음 수를 소수로 선택하고 그 수의 배수들을 모두 지운다. 이 과정을 범위의 끈까지 반복하고 남아있는 수들이 소수이다.
import java.io.*;
import java.util.*;
public class Main1929 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
boolean[] isPrime = sieveOfEratosthenes(N);
StringBuffer sb = new StringBuffer();
for (int i = M; i <= N; i++) {
if (isPrime[i])
sb.append(i).append('\n');
}
bw.write(sb.toString());
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' 카테고리의 다른 글
[백준 자바] 4948번(베르트랑 공준) (0) | 2024.06.23 |
---|---|
[백준 자바] 11653번(소인수분해) (0) | 2024.06.23 |
[백준 자바] 2581번(소수) - 에라토스테네스의 체 (0) | 2024.06.23 |
[백준 자바] 1978번(소수 찾기) (0) | 2024.06.22 |
[백준 자바] 1264번(모음의 개수) (0) | 2024.06.22 |