[BOJ] 백준 1978번 소수 찾기, 2581번 소수 - JAVA 자바 풀이

개요

 1978번은 주어진 숫자 N개 중 소수를 찾는 문제이고, 2581번은 주어진 범위 M부터 N까지의 숫자 중 소수(+ 최소값)를 찾는 문제입니다. 두 문제 모두 소수를 찾는 문제로, 저는 두 가지 방법으로 문제를 해결했습니다.

1. O(N^2)의 시간 복잡도를 갖는 단순 구현
2. O(N)의 시간 복잡도를 갖는 에라토스테네스의 체

https://www.acmicpc.net/step/10

 

사실 단계 별로 풀어보기의 문제 설명에는 첫 번째 방법이 작성되어 있습니다.

그러나 에라토스테네스의 체 방법으로도 풀이가 가능합니다.

 

위: 에라토스테네스의 체 / 아래: 단순 구현

 

시간과 메모리 상 큰 차이는 보이지 않는 것 같은데, 입력 값의 범위가 작아서 그렇습니다.

제출한 코드로 숫자 범위를 넓혀 테스트한 결과 큰 차이가 있었습니다.

 

M=1, N=10만

M=1, N=100만

 

단순 구현은 M=1, N=10만에서 약 2초가 걸렸고 M=1, N=100만에서 약 23초가 걸렸습니다.

 

M=1, N=10만

M=1, N=100만

 

반면 에라토스테네스의 체의 경우 M=1, N=10만에서 약 0.2초가 걸렸고, 놀랍게도 M=1, N=100만에서도 약 0.2초가 소요되었습니다.

 

소수란?

본격적으로 문제 풀이에 앞서 소수란 무엇인지 알아보겠습니다.

 

소수란 1과 자기 자신을 제외하면 약수가 존재하지 않는 수를 말합니다.

예를들어 2, 3, 5, 7과 같은 수는 1과 자신을 제외하면 나눌 수 있는 수가 존재하지 않습니다.

 

어떤 수가 소수인지 아닌지 알기 위해서는 위 정의를 그대로 사용하면 됩니다.

2부터 자신-1 까지의 수로 나눠지는지 아닌지 판단하면 되는 것이죠.

 

코드로 구현하자면 다음과 같습니다.

public boolean isPrimeNum(int N) {
    for(int i=2; i<N; i++) {
        if(N % 2 == 0) {
            return false;
        }
    }
}

 

1978번 소수 찾기

 이 문제는 단순 구현으로 풀어보았습니다. 주어진 숫자 마다 2부터 자신/2 까지 나눌 수 있는 수가 없다면 소수라고 판단하면 됩니다.

 

위에서는 자신-1 까지의 범위를 보라고 했는데 왜 이번에는 자신/2 까지 일까요?

숫자 10의 경우를 살펴보겠습니다.

 

10의 약수는 1, 2, 5, 10 입니다. 10의 절반인 5를 뒤따르는 숫자들 즉, 6부터는 10의 약수가 될 수 없습니다.

때문에 2부터 자신/2 까지의 숫자의 범위 내 약수가 존재하는지 아닌지 검사하면 됩니다.

public 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));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cnt = 0; // 소수 개수 카운트

        while(st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            boolean isPrime = true;

            if(num == 1)
                isPrime = false;

            for(int i=2; i<=num/2; i++) // 2부터 num/2 까지의 숫자들에 대해
                if(num % i == 0) { // 나눠지는 숫자가 존재한다면 소수가 아님
                    isPrime = false;
                    break;
                }

            if(isPrime)
                cnt++;
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
    }
}

 

2581번 소수

 이 문제는 에라토스테네스의 체를 이용해 풀어보았습니다. 에라토스테네스의 체의 더 자세한 설명은 🔗이 포스팅을 통해 보실 수 있습니다.

 

1. 숫자가 소수인지 아닌지를 저장할 isPrime 배열을 N의 크기로 생성한다.
2. 2부터 루트N 까지 범위 내 존재하는 소수 i 에 대하여
3. 해당 소수의 제곱부터 N 까지 범위 내 존재하는 소수의 배수 j 는 소수가 아님을 마킹한다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
        br.close();

        boolean[] isPrime = new boolean[N + 1];
        Arrays.fill(isPrime, true); // 최초에는 모든 수가 소수라고 true로 채운다.
        isPrime[1] = false; // 1은 소수가 아니므로 false 표기한다.

        for (int i = 2; i * i <= N; i++) { // 2부터 루트N 까지의 소수 i에 대해
            if(!isPrime[i])
                continue;

            for (int j = i * i; j <= N; j += i) { // i제곱 부터 N까지 소수 i의 배수 j를 false 표기한다.
                isPrime[j] = false;
            }
        }

        int min = 0;
        int sum = 0;

        for(int i=M; i<=N; i++)
            if(isPrime[i] == true) {
                if (min == 0) {
                    min = i;
                }
                sum += i;
            }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if(sum==0) // 소수가 없다면 -1을 출력하고
            bw.write("-1");
        else // 소수가 존재하면 합과 최솟값을 출력한다.
            bw.write(sum + "\n" + min);
        bw.flush();
        bw.close();
    }
}

 

문제 링크

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