[백준/JAVA]2581번 소수

문제

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

M부터 N까지 자연수 중에서 소수인 수들의 합과 최솟값을 구하는 문제였다.

문제 풀이

1. 내가 생각한 풀이

내가 생각한 방법은 이해하기 쉽고 로직이 명확하지만 숫자가 커질수록 반복 횟수가 매우 많아져 속도가 느려진다는 단점이 있다.

import java.io.*;
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());
        int sum=0, min=Integer.MAX_VALUE;
       
        for(int i=M;i<=N;i++){
            int count=0;
            for(int j=1;j<=i;j++){ //약수의 개수 세기
                if(i%j==0) count++;
            }
            
            if(count==2) { //약수가 2개라면(1은 자동으로 제외)
                sum+=i; 
                min=(min>i)?i:min; 
            }
        }
        
        if(sum==0){ //소수가 없다면 -1 출력
            System.out.println(-1);
        }else{
            System.out.println(sum);
            System.out.println(min);
        }
	}
}

2. 시간복잡도를 고려한 풀이

2-1. 제곱근까지만 검사

소수를 판별할 때 모든 수로 나눠볼 필요는 없다. 만약 num이 어떤 수로 나누어떨어진다면 그 약수 쌍(a × b = num) 중 하나는 반드시 √num 이하이기 때문에 2 ~ √num까지만 나눠보면 충분하다. 예를 들어 36의 약수 쌍은 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6) 이렇게 그 짝 중 한쪽이 반드시 √36 = 6 이하다.

import java.io.*;

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

        int sum = 0;
        int min = Integer.MAX_VALUE;

        for (int i = M; i <= N; i++) {
            if (isPrime(i)) {
                sum += i;
                min = Math.min(min, i); //min과 i를 비교해서 더 작은 수 반환
            }
        }

        if (sum == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
    }

    static boolean isPrime(int num) {
        if (num < 2) return false; //1은 소수가 아니므로 제외
        for (int i = 2; i <= Math.sqrt(num); i++) { //2부터 √num까지만 나눠보기
            if (num % i == 0) return false;
        }
        return true;
    }
}

2-2. 에라토스테네스의 체

2부터 시작해서 N까지의 숫자 중에서 소수만 골라내는 알고리즘이다. 핵심 아이디어는 어떤 수가 소수라면, 그 배수는 전부 소수가 아니다. 그래서 먼저 2는 소수니까 2의 배수는 다 지운다. 그 다음 3, 5, 7... 이런 식으로 반복한다.

예를 들어서 N이 36인 경우

i = 2일 때 2는 소수이므로 j = 4, 6, 8, ..., 36은 false

i = 3 일 때 3은 소수이므로 j = 9, 12, 15, ..., 36은 false

i = 4 일 때 4는 이미 false(2의 배수), 건너뜀

i = 5 일 때 5는 소수이므로 j = 25, 30, 35은 false

i = 6 일 때 6은 이미 false(2 × 3의 배수), 건너뜀

import java.io.*;

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

        boolean[] isPrime = new boolean[N + 1]; //true면 소수
        isPrime[0] = isPrime[1] = false; //0과 1은 소수 아님
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true; //기본적으로 모든 수는 소수로 설정
        }

        //에라토스테네스의 체 적용
        for (int i = 2; i * i <= N; i++) { //i<=√N == i<=Math.sqrt(num)
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false; //i의 배수는 소수가 아님
                }
            }
        }

        int sum = 0;
        int min = -1;

        //M부터 N까지 소수의 합과 최소값 구하기
        for (int i = M; i <= N; i++) {
            if (isPrime[i]) { //소수라면
                sum += i;
                if (min == -1) min = i; //첫 번째 소수는 최소값으로 설정
            }
        }

        if (sum == 0) {
            System.out.println(-1); //소수가 없으면 -1 출력
        } else {
            System.out.println(sum); 
            System.out.println(min); 
        }
    }
}

비교

1번 방법: i가 소수인지 보기 위해 1부터 i까지 전부 나눠본다.

2-1번 방법: i가 소수인지 보기 위해 √i 까지만 나눠보기 때문에 빠르다.

2-2번 방법: 전체 2~N 범위에서 소수를 미리 계산해서 배열에 저장한다. 많은 수의 소수를 빠르게 찾을 때 가장 효과적이다.