Programa Python para la Conjetura de Legendre

Dice que siempre hay un número primo entre cualquier cuadrado de dos números naturales consecutivos (n = 1, 2, 3, 4, 5, …). Esto se llama la Conjetura de Legendre . Conjetura: Una conjetura es una proposición o conclusión basada en información incompleta para la cual no se ha encontrado prueba, es decir, no se ha probado ni refutado.

Matemáticamente, siempre hay un primo p en el rango  donde  n es cualquier número natural. por ejemplo, 2 y 3 son los números primos en el rango  de  . 5 y 7 son los primos en el rango  de  . 11 y 13 son los primos en el rango  de  . 17 y 19 son los primos en el rango  de  .

Ejemplos:

Input : 4 
output: Primes in the range 16 and 25 are:
        17
        19
        23

Explicación : aquí 4 ² = 16 y 5 ² = 25 Por lo tanto, los números primos entre 16 y 25 son 17, 19 y 23.

Input : 10
Output: Primes in the range 100 and 121 are:
        101
        103
        107
        109
        113

# Python program to verify Legendre\'s Conjecture
# for a given n
 
import math
 
def isprime( n ):
     
    i = 2
    for i in range (2, int((math.sqrt(n)+1))):
        if n%i == 0:
            return False
    return True
     
def LegendreConjecture( n ):
    print ( "Primes in the range ", n*n
            , " and ", (n+1)*(n+1)
            , " are:" )
             
     
    for i in range (n*n, (((n+1)*(n+1))+1)):
        if(isprime(i)):
            print (i)
             
n = 50
LegendreConjecture(n)
 
# Contributed by _omg

Producción :

Primes in the range 2500 and 2601 are:
2503
2521
2531
2539
2543
2549
2551
2557
2579
2591
2593

Complejidad de tiempo : O(n*sqrtn). La función isPrime() toma el tiempo O(n) y está incrustada en la función LegendreConjecture() que también toma el tiempo O(n) ya que tiene un ciclo que comienza desde n ² y termina en 
(n+1) ²   entonces, (n+ 1) ² – n2 ⁼ 2n+1.

Espacio Auxiliar : O(1)

¡ Consulte el artículo completo sobre la conjetura de Legendre para obtener más detalles!