[JAVA / 자바] 백준 1929번 - 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

---

출력

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

---

 

---

문제 접근 방법

이번 문제는 n까지의 소수를 찾아 배열에 저장해 두고 m부터 n사이의 소수를 한 줄에 하나씩 오름차순으로 출력하면 되는 문제이다. 소수를 구할 때는 에라토스테네스의 체를 사용하면 편하게 소수를 구할 수 있다.

이번 문제의 유의할 점은 출력량이 많다는 것이다. JAVA에서는 출력을 흔히 대표적으로 많이 쓰이는 System.out.println함수를 사용하여 할 수도 있지만, BufferedWriter함수에 비해 시간 효율성이 훨씬 떨어진다. 따라서 이번 문제를 두 함수 버전으로 각각 풀어봄으로써 실행시간 차이를 보여보도록 하겠다.

---

JAVA 코드 풀이

- System.out.println Ver.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        boolean pN[] = new boolean[n+1];
        pN[1] = true;
        for(int i=2; i*i<=n; i++)
            if(!pN[i])
                for(int j=i*i; j<=n; j+=i)
                    pN[j] = true;
        for(int i=m; i<=n; i++){
            if(!pN[i])
                System.out.println(i);
        }
    }
}

System.out.println함수 사용 코드 결과

- BufferedWriter Ver.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException{
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        boolean pN[] = new boolean[n+1];
        pN[1] = true;
        for(int i=2; i*i<=n; i++)
            if(!pN[i])
                for(int j=i*i; j<=n; j+=i)
                    pN[j] = true;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=m; i<=n; i++){
            if(!pN[i])
                bw.write(i+"\n");
        }
        bw.close();
    }
}

BufferedWriter함수 사용 코드 실행 결과

---

후기

위 코드 실행 결과에서 보이듯이 거의 3배 가까이 차이를 보이게 된다. 출력량이 많아질수록 두 함수의 실행시간 차이는 점점 벌어지는데 출력량에 따라 융통성 있게 두 출력 함수를 상황에 맞게 사용해야겠다고 생각이 든다.

---

문제 원본

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