Se dice que un número n es un número de Carmichael si satisface la siguiente condición aritmética modular:
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
Dado un entero positivo n, encuentre si es un número de Carmichael. Estos números tienen importancia en el Método Fermat para las pruebas de primalidad .
Ejemplos:
Input : n = 8 Output : false Explanation : 8 is not a Carmichael number because 3 is relatively prime to 8 and (38-1) % 8 = 2187 % 8 is not 1. Input : n = 561 Output : true
La idea es simple, iteramos a través de todos los números del 1 al n y para cada número relativamente primo, verificamos si su potencia (n-1) en el módulo n es 1 o no.
A continuación se muestra un programa para verificar si un número dado es Carmichael o no.
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), " \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) + "</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("\n"); carmichaelnumber(561); printf("\n"); carmichaelnumber(1105); return 0; // This code is contributed by Susobhan Akhuli }
Producción:
0 1 1
Este artículo es una contribución de Ashutosh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA