[JAVA] 백준 1978번 소수찾기 🤎2 : 소수의 약수 범위에 대한 매우 중요한 생각!

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

 

백준 1978번 소수 찾기 문제를 풀 때에 소수에 관한 생각은 앞으로 소수 판별이 필요한 곳에 굉장히 많이 쓰일 것 같아 한번 정리 해보기로 했다.

 

문제는 말 그대로 소수면 카운팅해서 몇개인지 출력하는 문제이다

 

먼저 가장 먼저 든 생각은 소수의 정의가

1보다 크고 약수가 자신과 1 이외에 없는 수가 소수.

 

이니깐 그대로 한번 해보았다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            boolean isPrime = true;
            if(a == 1) isPrime = false;
            else{
                // 1보다 크고 약수가 자신과 1 이외에 없는 수가 소수.
                for (int j = 2; j < a; j++) {
                    if (a % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
            if(isPrime) count++;
        }
        System.out.println(count);
    }
}

 

나쁘지 않은 풀이라고 생각하지만  j=2부터 a까지 다 돌면서 자신이외에 약수가 있는지 체크해야 해서 시간이 꽤 걸린다는 단점이 있다. 그럼 다음 풀이를 한번 보고 생각해보자 위와 크게 다르지 않은데 범위의 차이가 있을 것이다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;

        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            if (isPrime(num)) {
                count++;
            }
        }
        
        System.out.println(count);
    }

    // 소수 판별 함수
    public static boolean isPrime(int num) {
        if (num <= 1) return false; // 1 이하의 수는 소수가 아님

        // 2부터 시작하여 √num까지 검사
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        
        return true;
    }
}

 

달라진 점은 소수 판별 하는 로직을 함수로 빼주었을 뿐이고 강조하고 싶은점은 i <= Math.sqrt(num) 이부분이다

소수의 약수들 판정범위를 제곱근보다 작거나 같은 범위까지 설정했다. 이부분을 수학적으로 봐보자.

 

수의 약수들이 제곱근보다 작거나 같은 이유는 다음과 같은 수학적 원리 때문이다:

어떤 자연수 n의 약수를 찾을 때, 약수 쌍 (a, b)를 고려할 수 있다. 즉, a * b = n을 만족하는 a와 b는 모두 n의 약수이다. 이때 a와 b는 다음의 특성을 가진다:

1. 대칭성: 약수들은 √n을 기준으로 대칭적인 관계를 가진다. 예를 들어, n = 36일 때 약수 쌍은 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)이다. 이 중에서 6은 √36이다.
2. 제곱근 기준: 약수 a가 √n보다 크다면, 대응되는 b는 반드시 √n보다 작다. 예를 들어, a가 √n보다 크면 b는 n/a로 계산되며, b는 √n보다 작아야 한다. 따라서, 만약 n이 약수 a와 b를 가지고 있다면, 둘 중 하나는 반드시 √n보다 작거나 같다.
3. 반례 방지: √n보다 큰 값만 검사할 경우, 대응되는 b가 이미 검사된 √n보다 작은 범위에 있기 때문에 추가로 검사할 필요가 없다. 즉, 제곱근까지만 약수를 검사해도 모든 약수 쌍을 고려한 것이 됩니다.
4. 결론은! √n 절반으로 나눠서 안쪽에 없으면 바깥쪽에 없고! 있으면 존재하고! 이런느낌!!!!

이러한 이유로 √n까지의 범위만 검사하면, n이 소수인지 확인하는 데 충분하다. 이는 효율적인 소수 판별 알고리즘을 작성할 수 있도록 해주는 수학적 근거이다.

 

그래서 이 범위를 설정하는 느낌을 꼭 알고가자! 시간단축이나 여러생각에 도움이 많이 된다.