费马素性判定法

给定一个数字 n，让我们检查它是否是素数。在之前的文章中，我们介绍并讨论了用于素性测试的“学校方法”。

在本文中，我们将探讨费马的方法。这是一种概率性方法，基于费马小定理。

[**费马小定理：**](https://www.geeksforgeeks.org/dsa/fermats-little-theorem/)
如果 n 是一个素数，那么对于每一个 a，其中 1 < a < n-1，

**a^(n-1) ? 1 (mod n)**
** 或者 **
**a^(n-1) **% n = 1 
 

示例：因为 5 是素数，所以 2^4 ? 1 (mod 5) [即 2^4 % 5 = 1]，
         3^4 ? 1 (mod 5) 以及 4^4 ? 1 (mod 5) 

         因为 7 是素数，所以 2^6 ? 1 (mod 7)，
         3^6 ? 1 (mod 7), 4^6 ? 1 (mod 7) 
         5^6 ? 1 (mod 7) 以及 6^6 ? 1 (mod 7) 

参考 [这里](https://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem) 了解不同的证明方法。

如果给定的数是素数，这个方法总是返回 true。如果给定的数是合数（即非素数），那么它可能返回 true 或 false，但对于合数产生错误结果的概率很低，并且可以通过增加迭代次数来降低这种概率。

下面是算法：

// k 值越高，对于合数输入得到正确结果的概率
// 就越高。对于素数输入，结果永远是正确的。
1)  重复执行以下步骤 k 次：
      a) 在范围 [2, n - 2] 内随机选择一个数 a
      b) 如果 gcd(a, n) ? 1，则返回 false
      c) 如果 a^(n-1) ≢ 1 (mod n)，则返回 false
2) 返回 true [大概是素数]。

推荐：请在查看解决方案之前，先在“练习”上尝试解决这个问题。

下面是该算法的实现。代码使用了来自 模幂运算 的 power 函数。

C++


CODEBLOCK_23ea274b


Java

`

// Java program to find the 
// smallest twin in given range

import java.io.*;
import java.math.*;

class GFG {
    
    /* Iterative Function to calculate
    // (a^n)%p in O(logy) */
    static int power(int a,int n, int p)
    {
        // Initialize result
        int res = 1;
        
        // Update ‘a‘ if ‘a‘ >= p
        a = a % p; 
    
        while (n > 0)
        {
            // If n is odd, multiply ‘a‘ with result
            if ((n & 1) == 1)
                res = (res * a) % p;
    
            // n must be even now
            n = n >> 1; // n = n/2
            a = (a * a) % p;
        }
        return res;
    }
    
    // If n is prime, then always returns true, 
    // If n is composite than returns false with 
    // high probability Higher value of k increases
    //  probability of correct result.
    static boolean isPrime(int n, int k)
    {
    // Corner cases
    if (n <= 1 || n == 4) return false;
    if (n  0)
    {
        // Pick a random number in [2..n-2]     
        // Above corner cases make sure that n > 4
        int a = 2 + (int)(Math.random() % (n - 4)); 
    
        // Fermat‘s little theorem
        if (power(a, n - 1, n) != 1)
            return false;
    
        k--;
        }
    
        return true;
    }
    
    // Driver Program 
    public static void ma