如果数字n满足以下模算术条件，则称其为卡迈克尔数：
null
power(b, n-1) MOD n = 1, for all b ranging from 1 to n such that b and n are relatively prime, i.e, gcd(b, n) = 1
给定一个正整数n，找出它是否是卡迈克尔数。这些数字对我们来说很重要 费马素性检验法 . 例如：
Input : n = 8Output : falseExplanation : 8 is not a Carmichael number because 3 is relatively prime to 8 and (38-1) % 8 = 2187 % 8 is not 1. Input : n = 561Output : true
这个想法很简单，我们迭代从1到n的所有数字，对于每个相对质数，我们检查它在模n下的（n-1）次方是否为1。 下面是一个程序，用于检查给定的数字是否为Carmichael。
C++
// A C++ program to check if a number is // Carmichael or not. #include <iostream> using namespace std; // utility function to find gcd of two numbers int gcd( int a, int b) { if (a < b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } // utility function to find pow(x, y) under // given modulo mod int power( int x, int y, int mod) { if (y == 0) return 1; int temp = power(x, y / 2, mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } // This function receives an integer n and // finds if it's a Carmichael number bool isCarmichaelNumber( int n) { for ( int b = 2; b < n; b++) { // If "b" is relatively prime to n if (gcd(b, n) == 1) // And pow(b, n-1)%n is not 1, // return false. if (power(b, n - 1, n) != 1) return false ; } return true ; } // Driver function int main() { cout << isCarmichaelNumber(500) << endl; cout << isCarmichaelNumber(561) << endl; cout << isCarmichaelNumber(1105) << endl; return 0; } |
JAVA
// JAVA program to check if a number is // Carmichael or not. import java.io.*; class GFG { // utility function to find gcd of // two numbers static int gcd( int a, int b) { if (a < b) return gcd(b, a); if (a % b == 0 ) return b; return gcd(b, a % b); } // utility function to find pow(x, y) // under given modulo mod static int power( int x, int y, int mod) { if (y == 0 ) return 1 ; int temp = power(x, y / 2 , mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1 ) temp = (temp * x) % mod; return temp; } // This function receives an integer n and // finds if it's a Carmichael number static int isCarmichaelNumber( int n) { for ( int b = 2 ; b < n; b++) { // If "b" is relatively prime to n if (gcd(b, n) == 1 ) // And pow(b, n-1)%n is not 1, // return false. if (power(b, n - 1 , n) != 1 ) return 0 ; } return 1 ; } // Driver function public static void main(String args[]) { System.out.println(isCarmichaelNumber( 500 )); System.out.println(isCarmichaelNumber( 561 )); System.out.println(isCarmichaelNumber( 1105 )); } } // This code is contributed by Nikita Tiwari. |
Python3
# A Python program to check if a number is # Carmichael or not. # utility function to find gcd of two numbers def gcd( a, b) : if (a < b) : return gcd(b, a) if (a % b = = 0 ) : return b return gcd(b, a % b) # utility function to find pow(x, y) under # given modulo mod def power(x, y, mod) : if (y = = 0 ) : return 1 temp = power(x, y / / 2 , mod) % mod temp = (temp * temp) % mod if (y % 2 = = 1 ) : temp = (temp * x) % mod return temp # This function receives an integer n and # finds if it's a Carmichael number def isCarmichaelNumber( n) : b = 2 while b<n : # If "b" is relatively prime to n if (gcd(b, n) = = 1 ) : # And pow(b, n-1)% n is not 1, # return false. if (power(b, n - 1 , n) ! = 1 ): return 0 b = b + 1 return 1 # Driver function print (isCarmichaelNumber( 500 )) print (isCarmichaelNumber( 561 )) print (isCarmichaelNumber( 1105 )) # This code is contributed by Nikita Tiwari. |
C#
// C# program to check if a number is // Carmichael or not. using System; class GFG { // utility function to find gcd of // two numbers static int gcd( int a, int b) { if (a < b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } // utility function to find pow(x, y) // under given modulo mod static int power( int x, int y, int mod) { if (y == 0) return 1; int temp = power(x, y / 2, mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } // This function receives an integer n and // finds if it's a Carmichael number static int isCarmichaelNumber( int n) { for ( int b = 2; b < n; b++) { // If "b" is relatively prime to n if (gcd(b, n) == 1) // And pow(b, n-1)%n is not 1, // return false. if (power(b, n - 1, n) != 1) return 0; } return 1; } // Driver function public static void Main() { Console.WriteLine(isCarmichaelNumber(500)); Console.WriteLine(isCarmichaelNumber(561)); Console.WriteLine(isCarmichaelNumber(1105)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to check if a // number is Carmichael or not. // utility function to find // gcd of two numbers function gcd( $a , $b ) { if ( $a < $b ) return gcd( $b , $a ); if ( $a % $b == 0) return $b ; return gcd( $b , $a % $b ); } // utility function to find // pow(x, y) under given modulo mod function power( $x , $y , $mod ) { if ( $y == 0) return 1; $temp = power( $x , $y / 2, $mod ) % $mod ; $temp = ( $temp * $temp ) % $mod ; if ( $y % 2 == 1) $temp = ( $temp * $x ) % $mod ; return $temp ; } // This function receives an integer // n and finds if it's a Carmichael // number function isCarmichaelNumber( $n ) { for ( $b = 2; $b <= $n ; $b ++) { // If "b" is relatively // prime to n if (gcd( $b , $n ) == 1) // And pow(b, n - 1) % n // is not 1, return false. if (power( $b , $n - 1, $n ) != 1) return 0; } return 1; } // Driver Code echo isCarmichaelNumber(500), " " ; echo isCarmichaelNumber(561), "" ; echo isCarmichaelNumber(1105), "" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to check if a number is // Carmichael or not. // utility function to find gcd of // two numbers function gcd(a, b) { if (a < b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } // utility function to find pow(x, y) // under given modulo mod function power(x, y, mod) { if (y == 0) return 1; let temp = power(x, parseInt(y / 2, 10), mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } // This function receives an integer n and // finds if it's a Carmichael number function isCarmichaelNumber(n) { for (let b = 2; b < n; b++) { // If "b" is relatively prime to n if (gcd(b, n) == 1) // And pow(b, n-1)%n is not 1, // return false. if (power(b, n - 1, n) != 1) return 0; } return 1; } document.write(isCarmichaelNumber(500) + "</br>" ); document.write(isCarmichaelNumber(561) + "</br>" ); document.write(isCarmichaelNumber(1105)); </script> |
C
// C Program to find if a number is Carmichael Number #include<stdio.h> int gcd( int a, int b) //Function to find GCD { if (a<b) return gcd(b, a); if (a % b == 0) return b; return gcd(b, a % b); } // Function to find pow(x,y) under given modulo mod int power( int x, int y, int mod) { if (y == 0) return 1; int temp = power(x, y / 2, mod) % mod; temp = (temp * temp) % mod; if (y % 2 == 1) temp = (temp * x) % mod; return temp; } //Function to find if received number n is a Carmichael number int carmichaelnumber( int n) { for ( int b=2;b<n;b++) { if (gcd(b,n)==1) if (power(b,n-1,n)!= 1) { printf ( "0" ); return 0; } } printf ( "1" ); return 0; }; int main() { carmichaelnumber(500); printf ( "" ); carmichaelnumber(561); printf ( "" ); carmichaelnumber(1105); return 0; // This code is contributed by Susobhan Akhuli } |
输出：
011
本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
