[JAVA / 자바] 백준 1978번 - 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

---

입력

첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

---

출력

주어진 수들 중 소수의 개수를 출력한다.

---

 

---

문제 접근 방법

수를 입력받아 그 수가 소수인지 판단만 해주면 되는 간단한 문제이다.

방법은 총 2가지인데

1. 수를 입력받을 때마다 그 수만 소수인지 판단한다.

2. 미리 나올 수 있는 수의 범위의 소수를 모두 구해두고 수를 입력받으면 그 수가 소수인지 아닌지 판단한다.

이때, 입력의 수에 따라 입력이 적을수록, 입력되는 수가 적을수록 1번 방법이 효율적이고 입력이 많을수록, 입력되는 수가 높을수록 2번 방법이 효율적이다.

입력의 수에 따라 효율성이 나눠진다면 Scanner함수와 BufferedReader함수로 짜인 코드의 효율성 비교도 빼놓을 수 없을 것이다. 따라서, 이번 문제는 총 4가지 방법으로 풀 예정이다.

1. Scanner + 1번

2. Scanner + 2번

3. BufferedReader + 1번

4. BufferedReader + 2번

이번 문제는 출력이 단 한 번밖에 없으므로 System.out.println() 함수와 BufferedWriter함수의 비교는 하지 않겠다.

---

JAVA 코드 풀이

1. Scanner + 1번

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int isPN;
        int cnt=0;
        for(int i=0; i<num; i++){
            isPN = input.nextInt();
            for(int p=2; p<=isPN; p++){
                if(p == isPN){
                    cnt++;
                }
                if(isPN % p == 0){
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

Scanner + 1번 코드 실행 결과

2. Scanner + 2번

import java.util.*;

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

Scanner + 2번 코드 실행 결과

3. BufferedReader + 1번

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

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int isPN;
        int cnt=0;
        for(int i=0; i<num; i++){
            isPN = Integer.parseInt(st.nextToken());
            for(int p=2; p<=isPN; p++){
                if(p == isPN){
                    cnt++;
                }
                if(isPN % p == 0){
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

BufferedReader + 1번 코드 실행 결과

4. BufferedReader + 2번

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

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        boolean pN[] = new boolean[1001];
        pN[1] = true;
        for(int i=2; i*i<=1000; i++)
            if(!pN[i])
                for(int j=i*i; j<=1000; j+=i)
                    pN[j] = true;
        int cnt=0;
        String list[] = br.readLine().split(" ");
        for(int i=0; i<list.length; i++){
            if(!pN[Integer.parseInt(list[i])])
                cnt++;
        }
        System.out.println(cnt);
    }
}

BufferedReader + 2번 코드 실행 결과

---

후기

이번 문제는 입력이 100개 정도로 많은 편은 아니었다. 그러나 그 차이에도 1, 2의 코드 실행 시간이 3, 4의 코드 실행 시간보다 거의 2배 정도 긴 것을 알 수 있었다. Scanner함수와 BufferedReader함수의 효율성 차이는 크다는 것을 깨달았고, 입력의 조건에 따라 에라토스테네스의 체를 사용하여 소수를 미리 구해놓고 이 수가 소수인지 대조하는 것보다 그때그때 계산을 통해 소수인지 아닌지 판별하는 것이 빠를 수도 있다는 것을 깨달았다. 따라서 이번 문제로 얻은 교훈은

입력 조건에 따라 어떤 코드를 작성해야 효율적인 코드가 될지 고민하고 코드를 작성해야겠다고 생각했다.

---

문제 원본

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