[Baekjoon(JAVA) - Algorithm] 1978번: 소수 찾기

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

1978번: 소수 찾기

 

---

문제를 풀기 앞서,

소수는 1과 자기 자신만을 약수로 가져야 한다.

즉, 1과 자기 자신을 제외한 숫자를 해당 숫자에 나눠서 나온 나머지가 0이 있다면 그 수는 소수가 아니다.

따라서 소수를 구하기 위해 2부터 해당 숫자 전까지의 수를 하나씩 해당 수에 나누면서 구하려고 했다.

 

예를 들어, 7이라는 수가 주어졌다.

소수 계산	결과
7 % 2 = 1	약수X
7 % 3 = 1	약수X
7 % 4 = 1	약수X
7 % 5 = 1	약수X
7 % 6 = 1	약수X

위 표처럼 1과 자기 자신을 제외한 모든 수가 약수가 아니라면 해당 숫자 7은 소수가 된다.

하지만 이 방식은 처음부터 끝까지의 숫자를 사용해야 하므로 시간복잡도가 O(N)이 된다.

 

시간복잡도가 O(N)인 경우보다 좋은 방법이 있을 거라는 생각을 했다.

찾아보니 소수를 찾는 방법에도 O(N) 보다 좋은 방법이 있다.

 

1과 자기 자신을 제외한 숫자를 해당 숫자에 나눠보면 나머지가 자기 자신의 제곱근이 초과되는 숫자는 나오지 않는다.

예를 들어, 8이라는 숫자의 제곱근은 2√2이고, 약수는 1, 2, 4, 8 이다.

약수에서 1과 자기 자신을 제외하면 2, 4가 남는다. 여기서 4는 1, 2, 4를 약수로 갖고 있으므로 소수가 아니다.

즉, 제곱근 2√2 정수화 시켜서 2 보다 큰 수가 약수로 있으면 해당 숫자는 결국 소수가 아니게 된다. 아래 표를 보자.

소수 계산	결과
8 % 2 = 0	약수O
8 % 3 = 2	약수X
8 % 4 = 0	약수O
8 % 5 = 3	약수X
8 % 6 = 2	약수X
8 % 7 = 1	약수X

위 표까지 보면 소수를 판별할 때 제곱근 아래에서 판별이 된다는 뜻이다.

이 방식은 처음부터 제곱근까지만 구하면 되므로 시간복잡도가 O(√N)이 된다.

 

이 방법으로 문제를 풀어보자.

Answer

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int primeNumberCount = 0;
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int num = 0;
            for (int i = 0; i < N; i++) {
                num = Integer.parseInt(st.nextToken());
                if (isPrimeNumber(num)) {
                    primeNumberCount++;
                }
            }
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }
        System.out.println(primeNumberCount);
    }

    static boolean isPrimeNumber(int num) {
        int sqrt = (int)Math.sqrt(num);

        if (num == 1) {
            return false;
        }

        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}

 

Code Review

int primeNumberCount = 0;

주어진 수들 중 소수의 개수를 구하는 `primeNumberCount` 변수를 선언한다.

 

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    ...
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resources`로 try에 객체 자원을 받아서 try문이 끝나면 자원을 별도의 `br.close()`처리 없이 자동으로 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

int num = 0;
for (int i = 0; i < N; i++) {
    num = Integer.parseInt(st.nextToken());
    if (isPrimeNumber(num)) {
        primeNumberCount++;
    }
}

첫 줄은 수의 개수 N이 주어지므로 첫 행 `br.readLine()`을 `Integer.parseInt()` 메서드로 정수 변환하여 `N` 변수를 선언한다.

둘째 줄에 공백을 기준으로 자연수들이 있으므로 `StringTokenizer` 객체를 사용한다. 이때 인자로 두 번째 `br.readLine()`과 공백 구분자를 받는다.

 

for문에서 재사용할 `num` 변수를 선언한다.

for문을 주어진 수 N개까지 반복한다.

 

`st.nextToken()`으로 공백으로 구분된 자연수 하나를 순서대로 꺼내서 `Integer.parseInt()` 메서드로 정수 변환 후 `num`에 대입한다.

`isPrimeNumber(num)`의 값이 true. 즉, 소수일 경우 소수의 개수 `primeNumberCount` 값을 1씩 증가시킨다.

 

이제 `isPrimeNumber()` 소수인지 계산하는 메서드를 보자.

static boolean isPrimeNumber(int num) {
    int sqrt = (int)Math.sqrt(num);

    if (num == 1) {
        return false;
    }

    for (int i = 2; i <= sqrt; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

주어진 자연수의 제곱근을 구하기 위해 `Math.sqrt()`를 사용한다. 이때 나온 제곱근을 정수로 형변환한다.

예를 들어, num이 8이라면 8의 제곱근 2√2 = 2.828... -> 2가 된다. (간단하게 소수점 아래인 루트는 제외시키면 된다.)

 

자연수가 1이라면 제곱근이 아니므로 `return false`를 한다.

 

for문을 2부터 정수로 형변환한 제곱근까지 로직을 반복한다.

자연수 num을 2부터 형변환한 제곱근까지 차례로 나눠서 나온 나머지가 0이면 약수가 되므로 소수가 아니게 된다. 따라서 이 경우에는 바로 `return false`를 한다.

만약 이 로직을 다 통과했다면 약수가 없어서 소수가 되므로 `return true`를 한다.

 

System.out.println(primeNumberCount);

위에서 해당 자연수가 소수이면 값을 1씩 증가시킨 `primeNumberCount`를 출력한다.

 

Result