给定一个数字n，检查它是否为素数。我们介绍并讨论了集合1中的学校素性测试方法。 素性测试|第1组（介绍和学校方法） 本文讨论了费马的方法。该方法是一种基于费马小定理的概率方法。
null
Fermat's Little Theorem:If n is a prime number, then for every a, 1 < a < n-1,an-1 ≡ 1 (mod n) OR an-1 % n = 1 Example: Since 5 is prime, 24 ≡ 1 (mod 5) [or 24%5 = 1], 34 ≡ 1 (mod 5) and 44 ≡ 1 (mod 5) Since 7 is prime, 26 ≡ 1 (mod 7), 36 ≡ 1 (mod 7), 46 ≡ 1 (mod 7) 56 ≡ 1 (mod 7) and 66 ≡ 1 (mod 7) Refer this for different proofs.
如果给定的数字是素数，那么这个方法总是返回true。如果给定的数字是复合数（或非素数），那么它可能返回true或false，但为复合数生成错误结果的概率很低，可以通过进行更多迭代来降低。
以下是算法：
// Higher value of k indicates probability of correct// results for composite inputs become higher. For prime// inputs, result is always correct1) Repeat following k times: a) Pick a randomly in the range [2, n - 2] b) If gcd(a, n) ≠ 1, then return false c) If an-1 ≢ 1 (mod n), then return false2) Return true [probably prime].
下面是上述算法的实现。该代码使用来自 模幂运算
C++
// C++ program to find the smallest twin in given range #include <bits/stdc++.h> using namespace std; /* Iterative Function to calculate (a^n)%p in O(logy) */ int power( int a, unsigned int n, int p) { int res = 1; // Initialize result a = a % p; // Update 'a' if 'a' >= p while (n > 0) { // If n is odd, multiply 'a' with result if (n & 1) res = (res*a) % p; // n must be even now n = n>>1; // n = n/2 a = (a*a) % p; } return res; } /*Recursive function to calculate gcd of 2 numbers*/ int gcd( int a, int b) { if (a < b) return gcd(b, a); else if (a%b == 0) return b; else return gcd(b, a%b); } // 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. bool isPrime(unsigned int n, int k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Try k times while (k>0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 int a = 2 + rand ()%(n-4); // Checking if a and n are co-prime if (gcd(n, a) != 1) return false ; // Fermat's little theorem if (power(a, n-1, n) != 1) return false ; k--; } return true ; } // Driver Program to test above function int main() { int k = 3; isPrime(11, k)? cout << " true" : cout << " false" ; isPrime(15, k)? cout << " true" : cout << " false" ; return 0; } |
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 <= 3 ) return true ; // Try k times while (k > 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 main(String args[]) { int k = 3 ; if (isPrime( 11 , k)) System.out.println( " true" ); else System.out.println( " false" ); if (isPrime( 15 , k)) System.out.println( " true" ); else System.out.println( " false" ); } } // This code is contributed by Nikita Tiwari. |
Python3
# Python3 program to find the smallest # twin in given range import random # Iterative Function to calculate # (a^n)%p in O(logy) def power(a, n, p): # Initialize result res = 1 # Update 'a' if 'a' >= p a = a % p while n > 0 : # If n is odd, multiply # 'a' with result if n % 2 : res = (res * a) % p n = n - 1 else : a = (a * * 2 ) % p # n must be even now n = n / / 2 return res % p # 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 def isPrime(n, k): # Corner cases if n = = 1 or n = = 4 : return False elif n = = 2 or n = = 3 : return True # Try k times else : for i in range (k): # Pick a random number # in [2..n-2] # Above corner cases make # sure that n > 4 a = random.randint( 2 , n - 2 ) # Fermat's little theorem if power(a, n - 1 , n) ! = 1 : return False return True # Driver code k = 3 if isPrime( 11 , k): print ( "true" ) else : print ( "false" ) if isPrime( 15 , k): print ( "true" ) else : print ( "false" ) # This code is contributed by Aanchal Tiwari |
C#
// C# program to find the // smallest twin in given range using System; 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 bool isPrime( int n, int k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Try k times while (k > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 Random rand = new Random(); int a = 2 + ( int )(rand.Next() % (n - 4)); // Fermat's little theorem if (power(a, n - 1, n) != 1) return false ; k--; } return true ; } static void Main() { int k = 3; if (isPrime(11, k)) Console.WriteLine( " true" ); else Console.WriteLine( " false" ); if (isPrime(15, k)) Console.WriteLine( " true" ); else Console.WriteLine( " false" ); } } // This code is contributed by divyesh072019 |
PHP
<?php // PHP program to find the // smallest twin in given range // Iterative Function to calculate // (a^n)%p in O(logy) function power( $a , $n , $p ) { // Initialize result $res = 1; // Update 'a' if 'a' >= p $a = $a % $p ; while ( $n > 0) { // If n is odd, multiply // 'a' with result if ( $n & 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. function isPrime( $n , $k ) { // Corner cases if ( $n <= 1 || $n == 4) return false; if ( $n <= 3) return true; // Try k times while ( $k > 0) { // Pick a random number // in [2..n-2] // Above corner cases // make sure that n > 4 $a = 2 + rand() % ( $n - 4); // Fermat's little theorem if (power( $a , $n -1, $n ) != 1) return false; $k --; } return true; } // Driver Code $k = 3; $res = isPrime(11, $k ) ? " true" : " false" ; echo ( $res ); $res = isPrime(15, $k ) ? " true" : " false" ; echo ( $res ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find the // smallest twin in given range /* Iterative Function to calculate // (a^n)%p in O(logy) */ function power( a, n, p) { // Initialize result let 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. function isPrime( n, k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Try k times while (k > 0) { // Pick a random number in [2..n-2] // Above corner cases make sure that n > 4 let a = Math.floor(Math.random()* (n-1 - 2) + 2); // Fermat's little theorem if (power(a, n - 1, n) != 1) return false ; k--; } return true ; } // Driver Code let k = 3; if (isPrime(11, k)) document.write( " true" + "</br>" ); else document.write( " false" + "</br>" ); if (isPrime(15, k)) document.write( " true" + "</br>" ); else document.write( " false" + "</br>" ); </script> |
输出：
truefalse
该解的时间复杂度为O（k logn）。请注意，功率函数需要O（对数n）时间。 注意，即使我们增加迭代次数（更高的k），上述方法也可能失败。存在一些性质为每a
我们将很快讨论更多的素性测试方法。
参考资料： https://en.wikipedia.org/wiki/Fermat_primality_test https://en.wikipedia.org/wiki/Prime_number http://www.cse.iitk.ac.in/users/manindra/presentations/FLTBasedTests.pdf https://en.wikipedia.org/wiki/Primality_test 本文由 阿杰 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
