📔문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
📝입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.
(1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
📺출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
📝예제 입력 1
3 16📺예제 출력 1
3
5
7
11
13🔍출처
-데이터를 추가한 사람: jinjean0123, yongjun042
🧮알고리즘 분류
- 수학
- 정수론
- 소수 판정
- 에라토스테네스의 체
📃소스 코드
import java.io.*;
import java.util.ArrayList;
public class Code1929 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] tem=br.readLine().split(" ");
int M=Integer.valueOf(tem[0]);
int N=Integer.valueOf(tem[1]);
br.close();
ArrayList<Boolean> prime=new ArrayList<>();
prime.add(false);
prime.add(false);
for(int i=2;i<=N;i++){//일단 사이에 수 저장
prime.add(i,true);
}
for(int i=2; (i*i)<=N; i++){
if(prime.get(i)){
for(int j = i*i; j<=N; j+=i) { //배수들
prime.set(j, false);
}
}
}
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
for(int j=M;j<=N;j++){
if(prime.get(j)==true){
bw.write(String.valueOf(j)+"\n");
}
}
bw.flush();
bw.close();
}
}
📰출력 결과
📂고찰
for(int i=2; (i*i)<=N; i++){
if(prime.get(i)){
for(int j = i*i; j<=N; j+=i) { //배수들
prime.set(j, false);
}
}
}이 부분이 매우 중요했다. 배수들은 다 false로 지정하는 코드이다.
각 소수들의 배수들만!
만약 i=2라면, 이중for문 안에서 2를 제외한 2의 배수들이 제거된다.
(i*i)<=2는 마지막 수를 넘지않는 배수까지만 체크하기 위함이다!
에라토스테네스의 체
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
MySQL DBA 신입