[백준] 2581번: 소수 - JAVA

[작성일: 2023. 09. 28]

 

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

 

 

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int sum = 0;
        int min = 0;

        for (int i = m; i <= n; i++) {
            boolean check = true;
            if (i == 1) {
                check = false;
                continue;
            }
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    check = false;
                    break;
                }
            }
            if (check) {
                sum += i;
                if (min == 0) {
                    min = i; // 처음 발견한 소수만 저장
                }
            }
        }

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

 

처음 이 문제를 이중 for문에서 j=2; j<i; j++ 로 풀었었다. 근데 이렇게 되면 i의 끝까지 가야해서 코드가 비효율 적이라고 한다.

 

소수를 찾는 알고리즘 문제에서는 Math클래스의 sqrt를 사용해서 n의 제곱근까지만 확인해도 된다고 한다.

 

만약 n이 소수가 아니라면 n을 나눌 수 있는 어떤 x가 반드시 루트 n 이하에 존재한다.

x가 루트n보다 크다면 n/x는 루트n보다 작을 것이고, 그러면 이미 검사된 숫자 중 하나로 n을 나눌 수 있는 것이므로 n은 소수가 아니게 된다.

 

예를 들어 61의 경우, 2부터 루트 61(대략 7.81, 정수 7)까지 나누어보고 나머지가 모두 0이 아니면 61은 소수가 된다. 61은 실제로 소수이며 2부터 7까지 어떤 수로도 나누어 떨어지지 않는다. 

 

실제로 두 가지 방법 전부 정답으로 나오지만 정답 제출 시간에 차이가 있는 것을 확인할 수 있었다.