Un entero p mayor que uno es primo si y solo si los únicos divisores de p son 1 y p. Los primeros números primos son 2, 3, 5, 7, 11, 13, …
La prueba de Lehmann es una prueba de primalidad probabilística para un número natural n, puede probar la primalidad de cualquier tipo de número (ya sea que un número impar grande sea primo o no). La prueba de Lehmann es una variación de la prueba de primalidad de Fermat.
El enfoque utilizado es el siguiente:
Si ‘n’ es un número impar y ‘a’ es un entero aleatorio menor que n pero mayor que 1, entonces
x = (a^((n-1)/2)) (mod n)
esta computado
- Si x es 1 o -1 (o n-1), entonces n puede ser primo.
- Si x no es 1 o -1 (o n-1), entonces n definitivamente es compuesto.
El hecho de que cualquier número compuesto pueda resultar primo, en este caso, depende del valor aleatorio ‘a’. Si todos los valores de a y n son coprimos, entonces n puede decirse que es un número primo.
Example-1: Input: n = 13 Output: 13 is Prime Explanation: Let a = 3, then, 3^((13-1)/2) % 13 = 729 % 13 = 1 Hence, 13 is Prime. Example-2: Input: n = 91 Output: 91 is Composite Explanation: Let a = 3, then, 3^((91-1)/2) % 91 = 27 Hence, 91 is Composite.
C++
// C++ code for Lehmann's Primality Test
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
#include<bits/stdc++.h>
using namespace std;
// function to check Lehmann's test
int lehmann(int n, int t)
{
// generating a random base less than n
int a = 2 + (rand() % (n - 1));
// calculating exponent
int e = (n - 1) / 2;
// iterate to check for different base values
// for given number of tries 't'
while(t > 0)
{
// calculating final value using formula
int result =((int)(pow(a, e)))% n;
//if not equal, try for different base
if((result % n) == 1 || (result % n) == (n - 1))
{
a = 2 + (rand() % (n - 1));
t -= 1;
}
// else return negative
else
return -1;
}
// return positive after attempting
return 1;
}
// Driver code
int main()
{
int n = 13 ; // number to be tested
int t = 10 ; // number of tries
// if n is 2, it is prime
if(n == 2)
cout << "2 is Prime.";
// if even, it is composite
if(n % 2 == 0)
cout << n << " is Composite";
// if odd, check
else
{
int flag = lehmann(n, t);
if(flag ==1)
cout << n << " may be Prime.";
else
cout << n << " is Composite.";
}
}
// This code is contributed by chitranayal
Java
// Java code for Lehmann's Primality Test
// importing "random" for random operations
import java.util.Random;
class GFG
{
// function to check Lehmann's test
static int lehmann(int n, int t)
{
// create instance of Random class
Random rand = new Random();
// generating a random base less than n
int a = rand.nextInt(n - 3) + 2;
// calculating exponent
float e = (n - 1) / 2;
// iterate to check for different base values
// for given number of tries 't'
while(t > 0)
{
// calculating final value using formula
int result = ((int)(Math.pow(a, e))) % n;
// if not equal, try for different base
if((result % n) == 1 || (result % n) == (n - 1))
{
a = rand.nextInt(n - 3) + 2;
t -= 1;
}
// else return negative
else
return -1;
}
// return positive after attempting
return 1;
}
// Driver code
public static void main (String[] args)
{
int n = 13; // number to be tested
int t = 10; // number of tries
// if n is 2, it is prime
if(n == 2)
System.out.println(" 2 is Prime.");
// if even, it is composite
if(n % 2 == 0)
System.out.println(n + " is Composite");
// if odd, check
else
{
long flag = lehmann(n, t);
if(flag == 1)
System.out.println(n + " may be Prime.");
else
System.out.println(n + " is Composite.");
}
}
}
// This code is contributed by AnkitRai01
Python3
# Python code for Lehmann's Primality Test
# importing "random" for random operations
import random
# function to check Lehmann's test
def lehmann(n, t):
# generating a random base less than n
a = random.randint(2, n-1)
# calculating exponent
e =(n-1)/2
# iterate to check for different base values
# for given number of tries 't'
while(t>0):
# calculating final value using formula
result =((int)(a**e))% n
# if not equal, try for different base
if((result % n)== 1 or (result % n)==(n-1)):
a = random.randint(2, n-1)
t-= 1
# else return negative
else:
return -1
# return positive after attempting
return 1
# Driver code
n = 13 # number to be tested
t = 10 # number of tries
# if n is 2, it is prime
if(n is 2):
print("2 is Prime.")
# if even, it is composite
if(n % 2 == 0):
print(n, "is Composite")
# if odd, check
else:
flag = lehmann(n, t)
if(flag is 1):
print(n, "may be Prime.")
else:
print(n, "is Composite.")
C#
// C# code for Lehmann's Primality Test
using System;
class GFG
{
// function to check Lehmann's test
static int lehmann(int n, int t)
{
// create instance of Random class
Random rand = new Random();
// generating a random base less than n
int a = rand.Next(n - 3) + 2;
// calculating exponent
float e = (n - 1) / 2;
// iterate to check for different base values
// for given number of tries 't'
while(t > 0)
{
// calculating final value using formula
int result = ((int)(Math.Pow(a, e))) % n;
// if not equal, try for different base
if((result % n) == 1 ||
(result % n) == (n - 1))
{
a = rand.Next(n - 3) + 2;
t -= 1;
}
// else return negative
else
return -1;
}
// return positive after attempting
return 1;
}
// Driver code
public static void Main (String[] args)
{
int n = 13; // number to be tested
int t = 10; // number of tries
// if n is 2, it is prime
if(n == 2)
Console.WriteLine(" 2 is Prime.");
// if even, it is composite
if(n % 2 == 0)
Console.WriteLine(n + " is Composite");
// if odd, check
else
{
long flag = lehmann(n, t);
if(flag == 1)
Console.WriteLine(n + " may be Prime.");
else
Console.WriteLine(n + " is Composite.");
}
}
}
// This code is contributed by Rajput-Ji
Producción:
13 may be Prime.
Publicación traducida automáticamente
Artículo escrito por Vidit_Gupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA