素数性质总结：
miller素数测试法:
一.费马小定理
如果n是素数，且gcd(a,n)==1,那么a(n-1)==1(mod n);
费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael.
前3个Carmichael数是561,1105,1729。
Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。
为此又有二次探测定理,以确保该数为素数:
二.二次探测定理
二次探测定理:如果p是一个素数，0<x<p,则方程x2≡1(mod p)的解为x=1,p-1
题目集合：
hdu 2138 How many prime numbers http://acm.hdu.edu.cn/showproblem.php?pid=2138 虽然这题比较水，可以直接判断sqrt(n)以内的数是否可以被n整除来判断n是否为素数。但如果用miller素数测试法来做的话还是挺好的一个训练题。不过坑点也蛮多的，我用g++编译相同的代码就tle，而c++就可以刚好过，具体的代码中有标识
/************************************************************** Problem:hdu 2138 User: youmi Language: C++ Result: Accepted Time:764MS Memory:1732K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <ctime> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d\n",a) #define ptlld(a) printf("%I64d\n",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int N; //下面分别是判15次和判10次的时间差别 const int Times=15;//998MS 1728K //const int Times=10 764MS 1732K ll mod_mul(ll a,ll b,ll mod) { ll res=0; a%=mod; while(b) { if(b&1) res=(res+a)%mod; b>>=1; a=(a<<1)%mod; } return res; } ll mod_exp(ll a,ll b,ll mod) { ll res=1; a%=mod; while(b) { if(b&1) res=mod_mul(res,a,mod); b>>=1; a=mod_mul(a,a,mod); } return res; } bool miller_rabin(ll n) { if(n==2||n==3||n==5||n==7||n==11) return true; if(n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0) return false; int tot=0; ll u=n-1; //要求x^u % n while(!(u&1))//如果u为偶数则u右移，用tot记录移位数，然后可以利用x^2==1来进行tot次二次判定， { tot++;u>>=1; } rep1(i,Times)//进行Times次测试 { ll x=rand()%(n-2)+2;//在[2, n)中取随机数 if(x==n) continue; x=mod_exp(x,u,n);//先计算(x^u) % n ll pre=x; rep0(j,tot)//把移位减掉的量补上，并在这地方加上二次探测 { x=mod_mul(x,x,n); if(x==1&&pre!=1&&pre!=n-1)//二次探测定理，这里如果x = 1则pre 必须等于 1，或则 n-1否则可以判断不是素数 return false; pre=x; } if(x!=1)//费马小定理 return false; } return true; } int main() { //freopen("in.txt","r",stdin); while(~sc(N)) { ll a; int cnt=0; srand(time(NULL));//随机数种子生成器 while(N--) { sclld(a); if(miller_rabin(a)) cnt++; } pt(cnt); } return 0; }
更新中
原文：http://www.cnblogs.com/youmi/p/4787734.html