```java package net.zhaoxuyang.common.algorithm.random; /** * * 蒙特卡羅算法 * <pre> * 設p是一個實數，且 0.5 小于 p 小于 1， * 如果蒙特卡羅算法對于問題的任一實例得到的正確解的概率不小于p，則稱該算法是正確的。 * </pre> * @author zhaoxuyang */ public class MonteCarlo { public static void main(String[] args) { //int[] array = {1, 2, 1}; // System.out.println(majority(array, array.length, 0.99)); // System.out.println(majority(array, array.length, 0.99)); System.out.println(checkPrimeByWilson(5)); System.out.println(checkPrimeByWilson(6)); while(true){ System.out.println(checkPrimeByMoteCarlo(97)); } } /** * 判斷一個數組是否存在主元素 一個含有n個元素的數組，當存在一個元素占比大于n/2時，稱該元素是數組的主元素。 */ static boolean majority(int[] array, double n, double p) { int k = (int) Math.ceil(Math.log(n) / Math.log(1 - 0.9)); for (int i = 1; i <= k; i++) { if (checkMajority(array, n)) { System.out.println(array[i]); return true; } } return false; } static boolean checkMajority(int[] array, double n) { int randomIndex = (int) (Math.random() * n); int item = array[randomIndex]; int k = 0; for (int i = 0; i < n; i++) { if (item == array[i]) { k++; } } return (k > 1.0 * n / 2); } /** * 常規的判斷一個數是否為素數 * * @param n * @return */ boolean checkPrime(long n) { int m = (int) Math.floor(Math.sqrt(n)); for (int i = 2; i <= m; i++) { if (n % i == 0) { return false; } } return true; } /** * * <pre> * Wilson定理有很高的理論價值，定義為：對于給定的正整數n，判定n是素數的充要條件是： * (n-1)! === -1(mod n) * 例如n = 5,6,7 * (5-1)!=24, 24 mod 5 = -1(mod 5)，故5是素數 * (6-1)!=120, 120 mod 6 = 0(mod 6)，故6不是素數 * (7-1)!=720, 720 mod 7 = -1(mod 7)，故6不是素數 * * </pre> * @param n * @return */ static boolean checkPrimeByWilson(long n) { return fan(n - 1) % n == n - 1; } static long fan(long n) { return n == 0 ? 1 : n * fan(n - 1); } static boolean checkPrimeByMoteCarlo(int n){ int m = (int) Math.floor(Math.sqrt(n)); int min = 2; int max = m - 1; int i = (int)(Math.random()*(max-min+1)+min); System.out.println(i); return n % i != 0; } } ```