核心做法是米勒罗宾定理。
测试n（n很大）
在（1，n-1）中选出一个a，1<=a<=n-1；
如果满足a^(n-1)%n==1;那么n有1/2的概率是素数；
如果不满足，那么n一定不是素数；
只需选取多个a，那么测试的正确率会无限接近100%
// 18位素数：154590409516822759 #include<stdio.h> typedef unsigned long long ll; ll mul(ll a,ll b,ll n) { ll ans=0; while(b) { if(b&1) ans=(ans+a)%n; a=(a+a)%n; b=b>>1; } return ans; } ll Pow(ll a,ll b,ll n) { ll result=1; ll base=a%n; while(b) { if(b&1) result=mul(result,base,n)%n; base=mul(base,base,n)%n; b=b>>1; } return result; } main() { ll n; scanf("%llu",&n); if(n<=73) { int i; for(i=2; i*i<=n; i++) if(n%i==0) break; if(i*i>n) printf("is prime\n"); else printf("isn't prime\n"); } ll pan[10] = {2, 3, 5, 7,11,31,61,73,233,331}; ll i; for(i=0; i<10; i++) if(Pow(pan[i],n-1,n)!=1)break;//if(pan[i]^(n-1)%n==1)this int is prime if(i==10)printf("is prime\n"); else printf("isn't prime\n"); }