'''
Tercera versión de un programa para mostrar números primos entre dos topes, alineados en 10 columnas.

Tanto para testear números como para buscar primos, se usa la conjetura de que todo primo se puede expresar como 6*N-1 o 6*N+1 para algún N entero positivo.
'''

# FUNCIONES

def primo(n):
    ''' Busca divisores impares de n hasta a lo sumo la parte entera de su raíz cuadrada. '''
    topeN = (int(n**0.5)+1)//6

    if n == 2: return True # caso especial del primer primo, que es par

    if n == 3: return True # caso especial del único primo impar que no se puede expresar como 6*N-1 o 6*N+1

    if n % 2 == 0: return False # caso especial de números pares, que son divisibles por 2 y por tanto no son primos
    
    N = 1

    while N <= topeN:
        posibleDivisor = 6*N-1
        if n % posibleDivisor == 0: return False
        posibleDivisor += 2 # posibleDivisor = 6*N+1
        if n % posibleDivisor == 0: return False
        N += 1

    return True # Si no terminó la función por encontrar un divisor dentro del ciclo repetitivo, es porque n es primo

# PROGRAMA

# PRÓLOGO
print('BÚSQUEDA DE NÚMEROS PRIMOS EN UN INTERVALO DE ENTEROS\n')

a = int(input('Ingrese un entero positivo mayor que 1 a partir del cual buscar números primos: '))
b = int(input('Ingrese otro entero positivo mayor que el previo para el tope de búsqueda: '))

print() # salto de línea

cantLínea = 0

if a == 2: # caso especial en el que se pidan primos desde el 2
    print(f'{a:10d}', end=' ')
    a = 3
    cantLínea += 1

if a == 3:
    print(f'{a:10d}', end=' ')
    a = 5
    cantLínea += 1

''' Como en este punto a>=5, se debe inicializar un candidato a partir de a, expresable como 6*N-1 o 6*N+1
P.e. si a es 1000
    6*N-1=1000; N=1001/6=166.833
    6*N+1=1000; N=999/6=166.5

    Si se toma N=ceil(1000/6)=167, se puede inicializar N como ceil(a/6)'''

from math import ceil
N = ceil(a/6)
candidato = 6*N-1
if candidato<a: candidato += 2

# DESARROLLO
while candidato <= b:
    if primo(candidato):
        print(f'{candidato:10d}', end=' ')

        cantLínea += 1
        if cantLínea == 10:
            cantLínea = 0
            print()
        
    if (candidato+1)%6 == 0: candidato += 2 # candidato era 6*N-1 y el nuevo será 6*N-1+2=6*N+1
    else:
        N += 1
        candidato = 6*N-1

# EPÍLOGO
input('\n\nPulse Intro/Enter para terminar')