Dado un número N y un número base A . La tarea es verificar si el número es un Pseudoprimo de Fermat a la base.
El número N se llama Pseudoprimo de Fermat a la base A, si
1. A > 1
2. N es un número compuesto
3. N divide A N-1 – 1.
Ejemplos:
Entrada: N = 645, a = 2
Salida: 1
645 = 3*5*43, por lo tanto, es un número compuesto
También 645 divide a 2^(644)-1
Por lo tanto, es un pseudoprimo de Fermat.
Entrada: N = 6, a = 2
Salida: 0
Enfoque: El enfoque consiste en verificar las siguientes condiciones:
- Compruebe si A > 1.
- Comprueba si N es un número compuesto .
- Comprueba si N divide A N-1 – 1.
Si todas las condiciones anteriores se cumplen, entonces N es un pseudoprimo de fermat para la base A.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if N is Fermat pseudoprime
// to the base A or not
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given number is composite
bool checkcomposite(int n)
{
// Check if there is any divisor of n less than sqrt(n)
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0)
return 1;
}
return 0;
}
// Effectively calculate (x^y) modulo mod
int power(int x, int y, int mod)
{
// Initialize result
int res = 1;
while (y) {
// If power is odd, then update the answer
if (y & 1)
res = (res * x) % mod;
// Square the number and reduce
// the power to its half
y = y >> 1;
x = (x * x) % mod;
}
// Return the result
return res;
}
// Function to check for Fermat Pseudoprime
bool Check(int n, int a)
{
// If it is composite and satisfy Fermat criterion
if (a>1 && checkcomposite(n) && power(a, n - 1, n) == 1)
return 1;
// Else return 0
return 0;
}
// Driver code
int main()
{
int N = 645;
int a = 2;
// Function call
cout << Check(N, a);
return 0;
}
Java
// Java program to check if N is Fermat pseudoprime
// to the base A or not
class GFG
{
// Function to check if
// the given number is composite
static boolean checkcomposite(int n)
{
// Check if there is any divisor of n
// less than sqrt(n)
for (int i = 2; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
return true;
}
}
return false;
}
// Effectively calculate (x^y) modulo mod
static int power(int x, int y, int mod)
{
// Initialize result
int res = 1;
while (y != 0)
{
// If power is odd,
// then update the answer
if ((y & 1) == 1)
{
res = (res * x) % mod;
}
// Square the number and reduce
// the power to its half
y = y >> 1;
x = (x * x) % mod;
}
// Return the result
return res;
}
// Function to check for Fermat Pseudoprime
static int Check(int n, int a)
{
// If it is composite and
// satisfy Fermat criterion
if (a > 1 && checkcomposite(n)
&& power(a, n - 1, n) == 1)
{
return 1;
}
// Else return 0
return 0;
}
// Driver Code
public static void main(String[] args)
{
int N = 645;
int a = 2;
// Function call
System.out.println(Check(N, a));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check if N is Fermat pseudoprime # to the base A or not from math import sqrt # Function to check if the given number is composite def checkcomposite(n): # Check if there is any divisor of n less than sqrt(n) for i in range(2,int(sqrt(n))+1,1): if (n % i == 0): return 1 return 0 # Effectively calculate (x^y) modulo mod def power(x, y, mod): # Initialize result res = 1 while (y): # If power is odd, then update the answer if (y & 1): res = (res * x) % mod # Square the number and reduce # the power to its half y = y >> 1 x = (x * x) % mod # Return the result return res # Function to check for Fermat Pseudoprime def Check(n,a): # If it is composite and satisfy Fermat criterion if (a>1 and checkcomposite(n) and power(a, n - 1, n) == 1): return 1 # Else return 0 return 0 # Driver code if __name__ == '__main__': N = 645 a = 2 # Function call print(Check(N, a)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to check if N is Fermat pseudoprime
// to the base A or not
using System;
class GFG
{
// Function to check if
// the given number is composite
static bool checkcomposite(int n)
{
// Check if there is any divisor of n
// less than sqrt(n)
for (int i = 2; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
return true;
}
return false;
}
// Effectively calculate (x^y) modulo mod
static int power(int x, int y, int mod)
{
// Initialize result
int res = 1;
while (y != 0)
{
// If power is odd, then update the answer
if ((y & 1) == 1)
res = (res * x) % mod;
// Square the number and reduce
// the power to its half
y = y >> 1;
x = (x * x) % mod;
}
// Return the result
return res;
}
// Function to check for Fermat Pseudoprime
static int Check(int n, int a)
{
// If it is composite and satisfy Fermat criterion
if (a > 1 && checkcomposite(n) &&
power(a, n - 1, n) == 1)
return 1;
// Else return 0
return 0;
}
// Driver code
static public void Main ()
{
int N = 645;
int a = 2;
// Function call
Console.WriteLine(Check(N, a));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript program to check if
// N is Fermat pseudoprime
// to the base A or not
// Function to check if the given
// number is composite
function checkcomposite(n)
{
// Check if there is any divisor
// of n less than sqrt(n)
for (let i = 2; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
return 1;
}
return 0;
}
// Effectively calculate (x^y) modulo mod
function power(x, y, mod)
{
// Initialize result
let res = 1;
while (y) {
// If power is odd, then update the answer
if (y & 1)
res = (res * x) % mod;
// Square the number and reduce
// the power to its half
y = y >> 1;
x = (x * x) % mod;
}
// Return the result
return res;
}
// Function to check for Fermat Pseudoprime
function Check(n, a)
{
// If it is composite and satisfy
// Fermat criterion
if (a>1 && checkcomposite(n) &&
power(a, n - 1, n) == 1)
return 1;
// Else return 0
return 0;
}
// Driver code
let N = 645;
let a = 2;
// Function call
document.write(Check(N, a));
</script>
Producción:
1
Complejidad del tiempo : O(sqrt(N))
Espacio Auxiliar: O(1)