https://www.acmicpc.net/problem/1929

📔문제

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는 마지막 수를 넘지않는 배수까지만 체크하기 위함이다!

에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.