1356.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1356 on 2005-09-24 at 15:17:17 */ 
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int Miller_Rabbin(long long);
long long modular_exp(long long, long long, long long);
long long gbc(long long, long long);

int main()
{
    long long a;
    
    while(scanf("%lld", &a) == 1) {
        if(a == 1 || a == 0) {
            printf("NO\n");
        } else if(a == 2) {
            printf("YES\n");
        } else {    
            if(Miller_Rabbin(a)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }    
    }

    return 0;
}                

int Miller_Rabbin(long long n)
{
    int test;
    long long a;
    srand(100);
    
    for(test = 0; test < 3; test++) {
        do {
            a = rand() % (n-1) + 2;
        } while(gbc(n, a) != 1);
        if(modular_exp(a, n-1, n) != 1) {
            return 0;
        }    
    }
    return 1;
}
long long modular_exp(long long a, long long b, long long n)
{
    long long d = 1; 
    int bin[32], num, i;
    
    for(num = 0; num < 32; num++) {
        if(b == 0) {
            break;
        }
        bin[num] = b % 2;
        b /= 2;
    }
    for(i = num-1; i >= 0; i--) {
        d = (d * d) % n;
        if(bin[i] == 1) {
            d = (d * a) % n;
        }
    }
    
    return d;
}
long long gbc(long long a, long long b)
{
    if(b == 1) {
        return 1;
    } else if(a % b == 0) {
        return b;
    } else {
        return gbc(b, (a%b));
    }
}