Carmichael skaičiai
Išbandykite GfG praktikoje 
#practiceLinkDiv { display: none !important; }
C++
#practiceLinkDiv { display: none !important; } Skaičius n laikomas Karmichaelio skaičiumi, jei jis atitinka šią modulinę aritmetinę sąlygą:
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
Duotas teigiamas sveikasis skaičius n, suraskite, ar tai yra Carmichael skaičius. Šie skaičiai yra svarbūs Fermato metodas pirmumo tyrimui .
Pavyzdžiai:
Input : n = 8 Output : false Explanation : 8 is not a Carmichael number because 3 is relatively prime to 8 and (3 8-1 ) % 8 = 2187 % 8 is not 1. Input : n = 561 Output : trueRecommended Practice Carmichael skaičiai Išbandykite!
Idėja paprasta, kartojame visus skaičius nuo 1 iki n ir kiekvienam santykinai pirminiam skaičiui patikriname, ar jo (n-1)-oji galia pagal modulį n yra 1, ar ne.
Žemiau yra programa, skirta patikrinti, ar nurodytas numeris yra Carmichael, ar ne.
C++
// A C++ program to check if a number is // Carmichael or not. #include 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 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 ) ' n ' ; echo isCarmichaelNumber ( 561 ) ' n ' ; echo isCarmichaelNumber ( 1105 ) ' n ' ; // 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 ) + ' ' ); document . write ( isCarmichaelNumber ( 561 ) + ' ' ); document . write ( isCarmichaelNumber ( 1105 )); < /script>
C // C Program to find if a number is Carmichael Number #include 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(xy) 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 ( ' n ' ); carmichaelnumber ( 561 ); printf ( ' n ' ); carmichaelnumber ( 1105 ); return 0 ; // This code is contributed by Susobhan Akhuli }
Išvestis:
0 1 1
Laiko sudėtingumas: O(n log n)
Pagalbinė erdvė: O(n)
