소수 판별법(밀러-라빈 소수판별법)

알고리즘 설명

연습 문제 : https://www.acmicpc.net/problem/5615

5615번: 아파트 임대

 

소스코드

#include <stdio.h>
#define NMAX 7
#define lint unsigned long long int
 
int N, cnt;
lint K;
 
int prime[NMAX] = {2, 3, 5, 7, 11, 13, 17};
 
lint pow(lint x, lint k, lint p) {
    if(k == 0) return 1;
    else if(k == 1) return x;
    else {
        if(k%2 == 0) return pow((x*x)%p, k/2, p);
        else return (pow((x*x)%p, k/2, p)*x)%p;
    }
}
 
// 소수인지 판단
bool isPrime(lint p) {
    lint a, s, r;
 
    for(int i=0;i<NMAX;i++) {
        if(p%prime[i] == 0) return 1;
 
        a = prime[i];
        s = p-1; // s = d*2^k
 
        while(1) {
            r = pow(a, s, p)%p;
 
            // a^s % p = -1
            if(r == p-1) break;
            else {
                if(s%2 == 0) s /= 2;
                else {
                    // a^d % p = 1 or -1 >> 소수
                    if(r == 1 or r == p-1) break;
                    else return 0;
                }
            }
        }
    }
 
    return 1;
}
 
int main() {
    scanf("%d", &N);
    while(N--) {
        scanf("%lld", &K);
        K = K*2+1;
 
        if( K==2 or (K%2==1 and isPrime(K)) ) cnt++;
    }
 
    printf("%d", cnt);
 
}

참고 자료

위키피디아 : https://ko.wikipedia.org/wiki/밀러-라빈_소수판별법

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

블로그 : https://freshrimpsushi.github.io/posts/miller-rabin-test/

밀러-라빈 판정법