[Algorithm] 소수 빠르게 찾는 법

20 Mar 2025 in Algorithm

소수를 빠르게 효율적으로 찾는 방법 3가지를 알아보자

1. 기본 소수 판별
2. 에라토스테네스의 체
3. Miller-Rabin 소수 판별법

---

1️⃣ 기본 소수 판별 (O(√N))

• 어떤 숫자 N이 소수인지 판별하는 가장 기본적인 방법은 1과 자기 자신을 제외한 다른 수로 나누어떨어지는지 확인하는 것
• 🔥 2부터 √N까지 나누어보자!
  • 소수가 아니라면 작은 약수를 가지고 있기 때문
• 코드 예제

public class PrimeCheck {
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPrime(29)); //true
        System.out.println(isPrime(100)); //false
    }
}

2️⃣ 에라토스테네스의 체 (O(N log log N))

여러 개의 소수를 빠르게 찾는 방법

• 1부터 N까지의 수 중에서 소수를 모두 찾아야 하는 경우
• 🔥 방법
  1. 2부터 시작해서 배수들을 모두 제거
  2. 남은 수들만 소수로 판별
• 장점
  • 한 번 계산해 두면 특정 범위 내에서 빠르게 소수 여부를 판별할 수 있음.
• 코드 예제

import java.util.*;

public class SieveOfEratosthenes {
    public static List<Integer> sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i*i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        //소수 리스트 생성
    }
}

3️⃣ Miller-Rabin 소수판별법 (O(log N))

소수 판별이 자주 필요할 때

• N이 엄청 크면 밀러-라빈 소수판별법을 사용해야함
  • 10^18이상의 큰 수가 소수인지 판별할 때
  • 암후학, 해시 관련 문제에서 사용
• 🔥 확률적 알고리즘
• 코드 예제

import java.util.Random;

public class MillerRabin {
    public static boolean isPrime(long n, int k) { // k는 테스트 횟수
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;

        // n - 1 = 2^r * d 형태로 변환
        long d = n - 1;
        int r = 0;
        while (d % 2 == 0) {
            r++;
            d /= 2;
        }

        Random rand = new Random();

        // Miller-Rabin 테스트 실행
        for (int i = 0; i < k; i++) {
            long a = 2 + rand.nextLong(n - 3); // 2 ≤ a ≤ n-2
            long x = powerMod(a, d, n); // x = a^d % n

            if (x == 1 || x == n - 1) continue;

            boolean isComposite = true;
            for (int j = 0; j < r - 1; j++) {
                x = powerMod(x, 2, n); // x = x^2 % n
                if (x == n - 1) {
                    isComposite = false;
                    break;
                }
            }

            if (isComposite) return false; // 합성수 판별
        }

        return true; // 소수 판별
    }

    // (base^exp) % mod 연산 (빠른 거듭제곱)
    private static long powerMod(long base, long exp, long mod) {
        long result = 1;
        base %= mod;

        while (exp > 0) {
            if ((exp & 1) == 1) { // 홀수 지수 처리
                result = (result * base) % mod;
            }
            base = (base * base) % mod; // 제곱
            exp >>= 1; // 지수 나누기 2
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(isPrime(15485863, 5));  // true (소수)
        System.out.println(isPrime(1000000007, 5)); // true (소수)
        System.out.println(isPrime(1000000008, 5)); // false (합성수)
    }
}