[백준 온라인 저지] 1929. 소수 구하기

1. 입력

- 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

- M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

2. 출력

- 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

3. 코드

1) 첫 코드(2023/04/20)

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int m = Integer.valueOf(token.nextToken()), n = Integer.valueOf(token.nextToken());
        for(int i=m; i<=n ; i++){
            boolean isPrime = i!=1;
            for(int j=2 ; j<=Math.sqrt(i) ; j++){
                if(i%j==0){
                    isPrime=false; break;
                }
            }
            if(isPrime) bw.write(i+"\n");
        }
        bw.flush();
        bw.close();
    }
}

- 21716KB, 608ms

 

2) 에라토스테네스의 체를 이용한 코드(2023/07/01)

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        // 입력 받기. 1 <= m <= n <= 1,000,000
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer token = new StringTokenizer(br.readLine());
        int m = Integer.valueOf(token.nextToken()), n = Integer.valueOf(token.nextToken());
        
        // 에라토스테네스의 체 이용
        boolean[] prime = new boolean[1000001];
        Arrays.fill(prime, true); prime[1] = false;
        for(int i=2 ; i<=1000000 ; i++)
            if(prime[i]){
                for(int j=2*i ; j<=1000000 ; j+=i)
                    prime[j] = false;
            }
        for(int i=m ; i<=n ; i++)
            if(prime[i]) bw.write(i+"\n");
        bw.flush();
        bw.close();
    }
}

- 24820KB, 344ms