BOJ/1929) 소수 구하기
소수 구하기(1929), Silver2
https://www.acmicpc.net/problem/1929
문제풀이
소수를 구하는 방법은 여러가지가 있지만, 에라토스테네스의 체를 활용하여 소수를 구하였다.
소수는 1과 자기 자신만을 약수로 갖는 수를 뜻한다. 따라서 소수가 아닌지(합성수인지)를 확인하려면 1과 자기자신 외 다른 수의 배수인지를 확인하면 된다.
결론은 에라토스테네스의 체는 소수를 찾고, 그 소수의 배수를 모두 지워나가는 방식으로 진행하면 된다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int M = Integer.parseInt(input[0]);
int N = Integer.parseInt(input[1]);
br.close();
boolean[] isPrime = new boolean[N + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
// 에라토스테네스의 체
for(int i = 2; i < N; i++) {
if (!isPrime[i]) continue;
for(int j = i + i; j <= N; j += i) {
isPrime[j] = false;
}
}
// 답 출력
for(int i = M; i <= N; i++) {
if (isPrime[i]) System.out.println(i);
}
}
}
Author And Source
이 문제에 관하여(BOJ/1929) 소수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@syeon-c/BOJ1929-소수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)