Hoj 1356 Prime Judge

本题我曾想以[1,500000]内的质因子为基础来判定整个int范围的质数，但是超时。
无奈用Miller Rabin算法吧。
根据 ：费尔马小定理，如果 n 为素数，那么对于小于n的数a有a^(n-1) = 1(mod n)
那么我们可以随机生成一个a（a<n），如果满足a^(n-1) = 1(mod n),那么n就有可能是质数。随机生成三次，即验证三次，那么这个概率就非常大。
关于a^b%n，用快速幂来解。
[cpp]  
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
  
using namespace std;  
  
long long mul(long long a,long long b)  
{  
    return a * b;  
}  
long long power(long long a,long long b,int n)  
{  
    //快速幂取模a^b%n  
    long long b_temp = b;  
    long long result = 1;  
  
    while(b_temp)  
    {  
        if(b_temp&1)  
        {  
            result = mul(result,a)%n;  
        }  
        a = mul(a,a)%n;  
        b_temp = b_temp>>1;  
    }  
    return result;  
}  
bool Miller_Rabbin(long long n)  
{  
    //费尔马小定理，如果 n 为素数，那么对于小于n的数a有a^(n-1) = 1(mod n)  
    long long a = rand()%(n-1)+1;//随机生成一个小于n的数  
  
    //a^(n-1) = 1(mod n)  
    if(power(a,n-1,n)!=1)  
    {  
        return false;  
    }  
    return true;  
}  
int main()  
{  
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin);  
#endif  
  
    long long n;  
    while(scanf("%lld",&n)!=EOF)  
    {  
        int flag = 1;//1表示素数  
        int times = 3;//times为每个数进行测试的次数  
        if(n<=1)  
        {  
            flag = 0;  
        }  
        else if(n==2||n==3)  
        {  
            flag = 1;  
        }  
        else  
        {  
            while(times--&&flag)  
            {  
                if(!Miller_Rabbin(n))  
                {  
                    flag = 0;  
                }  
            }  
        }  
        if(!flag)  
        {  
            printf("NO\n");  
        }  
        else  
        {  
            printf("YES\n");  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,