二次探測定理：如果是素數(shù)，且，則方程的解為或。

?

代碼：

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h>using namespace std; const int Times = 10; typedef long long LL;LL multi(LL a, LL b, LL m) {LL ans = 0;a %= m;while(b){if(b & 1){ans = (ans + a) % m;b--;}b >>= 1;a = (a + a) % m;}return ans; }LL quick_mod(LL a, LL b, LL m) {LL ans = 1;a %= m;while(b){if(b & 1){ans = multi(ans, a, m);b--;}b >>= 1;a = multi(a, a, m);}return ans; }bool Miller_Rabin(LL n) {if(n == 2) return true;if(n < 2 || !(n & 1)) return false;LL m = n - 1;int k = 0;while((m & 1) == 0){k++;m >>= 1;}for(int i=0; i<Times; i++){LL a = rand() % (n - 1) + 1;LL x = quick_mod(a, m, n);LL y = 0;for(int j=0; j<k; j++){y = multi(x, x, n);if(y == 1 && x != 1 && x != n - 1) return false;x = y;}if(y != 1) return false;}return true; }int main() {int T;scanf("%d",&T);while(T--){LL n;scanf("%I64d",&n);if(Miller_Rabin(n)) puts("Yes");else puts("No");}return 0; }

?

質(zhì)數(shù)檢測Java大數(shù)版：

?

題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1186

import java.io.*; import java.util.*; import java.math.BigInteger;public class Main{public static final int Times = 10;public static BigInteger quick_mod(BigInteger a,BigInteger b,BigInteger m){BigInteger ans = BigInteger.ONE;a = a.mod(m);while(!(b.equals(BigInteger.ZERO))){if((b.mod(BigInteger.valueOf(2))).equals(BigInteger.ONE)){ans = (ans.multiply(a)).mod(m);b = b.subtract(BigInteger.ONE);}b = b.divide(BigInteger.valueOf(2));a = (a.multiply(a)).mod(m);}return ans;}public static boolean Miller_Rabin(BigInteger n){if(n.equals(BigInteger.valueOf(2))) return true;if(n.equals(BigInteger.ONE)) return false;if((n.mod(BigInteger.valueOf(2))).equals(BigInteger.ZERO)) return false;BigInteger m = n.subtract(BigInteger.ONE);BigInteger y = BigInteger.ZERO;int k = 0;while((m.mod(BigInteger.valueOf(2))).equals(BigInteger.ZERO)){k++;m = m.divide(BigInteger.valueOf(2));}Random d = new Random();for(int i=0;i<Times;i++){int t = 0;if(n.compareTo(BigInteger.valueOf(10000)) == 1){t = 10000;}else{t = n.intValue() - 1;}int a = d.nextInt(t) + 1;BigInteger x = quick_mod(BigInteger.valueOf(a),m,n);for(int j=0;j<k;j++){y = (x.multiply(x)).mod(n);if(y.equals(BigInteger.ONE) && !(x.equals(BigInteger.ONE)) && !(x.equals(n.subtract(BigInteger.ONE)))) return false;x = y;}if(!(y.equals(BigInteger.ONE))) return false;}return true;}public static void main(String[] args){Scanner cin = new Scanner(System.in);while(cin.hasNextBigInteger()){BigInteger n = cin.nextBigInteger();if(Miller_Rabin(n)) System.out.println("Yes");else System.out.println("No");}} }

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的Miller-Rabin素数测试的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。