C - Prime number or not
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
Your task is simple.Give you a number N, you should judge whether N is a prime number or not.
Input
There are multiple test cases. For each test case, there is an integer N(2<=N<=10^18).
Output
For each test case, you should output whether N is a prime number or not.If N is a prime number , you should output "It is a prime number."; otherwise you should output "It is not a prime number.";
Sample Input
2 4
Sample Output
It is a prime number. It is not a prime number.
这里关键的问题在于数据达到了1亿亿，没办法用普通的方法进行运算，所以这里用到了米勒拉宾大素数判定方法。
算法流程：根据费马小定理，a^(n-1)mod n==1,1<a<n,n为奇素数。随机在1~n的范围内取一个数a，进行式子的判定，返回1，就是伪素数，否则就是合数。因为伪素数是素数 的可能性为3/4，也就是正确率是1-1/4^k，所以我们要按定一个k使得正确率尽可能得大。所以要多次重复取随机数，然后判定。
文字代码：
1：重复MAX次运算
2：在1~n中取得随机数a
3：计算a^(n-1)mod n？=1，在这个计算里，注意到n可能很大，所以a^(n-1)可能越界，就想到用快速幂来边乘，边取模，但是又发现在n很大的时候，a*a都有可能溢出，所以想到了用快速幂的方法，进行快速积取模，边加边取模。这里的两个快速可避免溢出
4：在3中可得到的数如果为1，则在循环未结束前继续从2开始操作，否则直接返回0，表示n是合数
5：如果上面的循环能完整做完，说明n已经是强伪素数，我们可以返回1，判定为素数。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 10
__int64 muti(__int64 a,__int64 b,__int64 m)
{
__int64 ans=;
while(b)
{
if(b&)
ans=(ans+a)%m;
a=*a%m;
b/=;
}
return ans;
}
__int64 pow(__int64 a,__int64 b,__int64 m)
{
__int64 ans=;
while(b)
{
if(b&)
ans=muti(ans,a,m);
a=muti(a,a,m);//二进制。快速幂的思想
b/=;
}
return ans;
}
int miller_rabin(long long n)
{
__int64 i,a;
if(n==)
return ;
if(n<||!(n&))
return ;
srand((unsigned)time(NULL));
for(i=;i<=MAX;i++)
{
a=rand()%(n-)+;
if(pow(a,n-,n)!=)
return ;
}
return ;
}
int main()
{
__int64 n;
while(scanf("%I64d",&n)!=EOF)
if(miller_rabin(n))
printf("It is a prime number.\n");
else printf("It is not a prime number.\n");
return ;
}