소수 판별 알고리즘

소수(prime number)는 많은 수학적 응용 분야에서 중요한 개념으로 활용됩니다. 이번 글에서는 소수를 판별하기 위한 다양한 알고리즘들을 살펴보겠습니다. Trial Division부터 Lucas-Lehmer까지 다양한 알고리즘을 통해 소수를 판별하는 방법을 알아보겠습니다.

---

소수 판별 알고리즘

• Trial Division은 가장 기본적인 소수 판별 알고리즘입니다.
  2부터 해당 수의 제곱근까지 나누어 떨어지는지 확인하여 소수를 판별합니다.
  
  
• Sieve of Eratosthenes는 소수를 미리 구하는 방법입니다.
  2부터 시작하여 배수를 지워나가면서 소수를 찾아냅니다.
  
  
• Fermat's Primality Test는 확률적인 소수 판별 알고리즘입니다.
  임의의 정수 a에 대해 a^(n-1) ≡ 1 (mod n)이 성립하면 n을 소수로 간주합니다.
  
  
• Lucas-Lehmer Primality Test는 특정한 형태의 Mersenne 소수에 대해서만 적용 가능한 알고리즘입니다.
  2^p - 1 형태의 Mersenne 소수에 대해서 Lucas-Lehmer 테스트를 수행하여 소수를 판별합니다.

 

소수 판별 알고리즘은 암호학, 수론 등 다양한 분야에서 활용되며, 효율적인 알고리즘 선택은 중요한 과제입니다.

---

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

// 소수 판별을 위한 알고리즘들

// Trial Division
int isPrimeTrialDivision(int n) {
   if (n <= 1)
      return 0;  // 1은 소수가 아님
   
   for (int i = 2; i <= sqrt(n); i++) {
      if (n % i == 0)
         return 0;  // 나누어 떨어지므로 소수가 아님
   }
   
   return 1;  // 소수임
}

// Sieve of Eratosthenes
int isPrimeSieve(int n) {
   if (n <= 1)
      return 0;  // 1은 소수가 아님
   
   int* sieve = (int*)malloc((n + 1) * sizeof(int));
   sieve[0] = sieve[1] = 0;
   
   for (int i = 2; i <= n; i++)
      sieve[i] = 1;
   
   for (int p = 2; p <= sqrt(n); p++) {
      if (sieve[p] == 1) {
         for (int i = p * p; i <= n; i += p)
            sieve[i] = 0;
      }
   }
   
   int result = sieve[n];
   free(sieve);
   return result;
}

// 페르마의 소정리 (Fermat's Primality Test)
int power(int x, unsigned int y, int p) {
   int res = 1;
   x = x % p;
   
   while (y > 0) {
      if (y & 1)
         res = (res * x) % p;
      y = y >> 1;
      x = (x * x) % p;
   }
   
   return res;
}

int isPrimeFermat(int n, int k) {
   if (n <= 1)
      return 0;  // 1은 소수가 아님
   
   if (n <= 3)
      return 1;  // 2와 3은 소수
   
   for (int i = 0; i < k; i++) {
      int a = 2 + rand() % (n - 4);
      
      if (power(a, n - 1, n) != 1)
         return 0;  // 합성수임
   }
   
   return 1;  // 확률적으로 소수일 가능성이 높음
}

// 루카스-레이먼드 소수 판별 알고리즘 (Lucas-Lehmer Primality Test)
int isPrimeLucasLehmer(int p) {
   if (p <= 1)
      return 0;  // 1은 소수가 아님
   
   if (p == 2)
      return 1;  // 2는 소수
   
   int s = 4;
   int m = (1 << p) - 1;
   
   for (int i = 3; i <= p; i++) {
      s = (s * s - 2) % m;
      
      if (s == 0)
         return 1;  // 소수임
   }
   
   return 0;  // 소수가 아님
}

int main() {
   int num;
   printf("정수를 입력하세요: ");
   scanf("%d", &num);
   
   printf("Trial Division: %d\n", isPrimeTrialDivision(num));  // Trial Division 알고리즘을 사용하여 소수 여부를 판별
   printf("Sieve of Eratosthenes: %d\n", isPrimeSieve(num));  // Sieve of Eratosthenes 알고리즘을 사용하여 소수 여부를 판별
   printf("Fermat's Primality Test: %d\n", isPrimeFermat(num, 5));  // Fermat's Primality Test 알고리즘을 사용하여 소수 여부를 판별
   printf("Lucas-Lehmer Primality Test: %d\n", isPrimeLucasLehmer(num));  // Lucas-Lehmer Primality Test 알고리즘을 사용하여 소수 여부를 판별
   
   return 0;
}

---

실행결과

작은 수

큰 수

오류 해결 과정 : 큰수 연산을 위해 gmp.h라이브러리를 사용하여 고정밀도연산을 하려고 했지만 라이브러리를 불러오는데에 실패해서 그냥 평범하게 int형으로 해결했습니다. 또한 위에 보이다시피 아래 두개의 알고리즘은 어차피 정확하지 않고, 위의 두개 알고리즘은 큰수에서는 시간이 너무 오래걸리기 때문에 큰 수 연산은 구현하지 않았습니다.