5

Estoy practicando un ejercicio para encontrar los números primos de la forma mas óptima posible.

La forma mas óptima que he conseguido hasta el momento es la siguiente:

#No se nada de funciones ni arrays

i = 1
parar_bucle = False

num = int(input("Dame un numero >> "))

while parar_bucle == False:
    if num % i == 0: #Si el resto del numero dado entre el indice da 0...
        if i != 1: #...El indice es diferente a 1...
            if i != num: #...Y también es diferente al numero dado (ej.: 7 != 7)
                parar_bucle = True #que pare el bucle e imprima el numero no es primo
                print("El numero no es primo")
    else: #Si no
        parar_bucle = True #que pare el bucle y escriba el numero es primo
        print("El numero es primo")
    i += 1 #indice suma 1

He probado con bucle for pero me he dado cuenta de que recorría todos los divisores, con while no los recorre todos y es mas óptimo pero creo que todavía esta practica se puede hacer mas óptima.

¿Existe una forma más óptima de realizar este bucle while?

¿Cómo puedo comprobar el tiempo que tarde en ejecutarse un programa?

3
  • 3
    ¿Responde esto a tu pregunta? Optimizar método para calcular números primos
    – Candid Moe
    Commented el 17 oct. 2020 a las 20:57
  • ¡Bienvenido a Stack Overflow en español! Mira Cómo preguntar para que tu pregunta sea mejor recibida. También, aprovecha y haz el recorrido para entender mejor cómo funcionamos y de paso obtener tu primera medalla!
    – RuDaHee
    Commented el 17 oct. 2020 a las 21:01
  • 1
    Tu algoritmo es es más óptimo posible para detectar primos si el número es realmente primo, pues lo detecta en una sola iteración del bucle. Por desgracia si el número no es primo falla y te dice que es primo, también en la primera iteración del bucle :-)
    – abulafia
    Commented el 17 oct. 2020 a las 21:02

1 respuesta 1

5

He desarrollado un algoritmo algo mas optimo sin hacer uso de funciones (def)

La diferencia fundamental esta en que no recorre todos los posibles divisores desde i al numero que estas comprobando.

En el momento en el que i es mayor a la mitad del numero nunca va a poder ser divisible, por tanto no tiene sentido seguir buscando.

También inicializo la variable i en 2 directamente, ahorrándome otra iteración del bucle.

te dejo el código por aquí abajo:

import math #Importante para la raíz cuadrada.

# Declaramos variables
primo = False
i = 2

# Dato de entrada
num = int(input("Dame un numero >> "))

# No se puede encontrar un divisor por encima de la raíz del numero
# con math.ceil() redondeamos hacia arriba (por ejemplo: 1.3 -> 2)
raiz_num = math.ceil(math.sqrt(num))


# Seguimos buscando mientras aun sea primo e 'i' sea menor que la raiz del numero.
while not(primo) and (i <= raiz_num):
    # Si encuentra un divisor.
    if num % i == 0:
        primo = True

    i += 1

# Damos el resultado por pantalla.
if not(primo):
    print('El numero es primo')
else:
    print('El numero no es primo')

EDITADO

Para conocer el tiempo que tarda la ejecución de un programa puedes usar la librería time. Te pongo un ejemplo muy visual para que lo entiendas rápidamente

import time # OBLIGATORIO PARA USAR LA LIBRERIA

tiempo_inicial = time.time()

#Lineas de codigo de tu programa

for i in range(999999):
    print(i)

tiempo_final = time.time()

print("mi programa ha tardado en ejecutarse: ", tiempo_final-tiempo_inicial, " segundos")

En mi caso la respuesta que me arroja es esta:

mi programa ha tardado en ejecutarse:  7.535167932510376  segundos

Gracias a @abulafia por el dato de que no se pueden encontrar divisores por encima de la raíz de un numero.

Espero haberte servido de ayuda.

3
  • 4
    En realidad basta con probar divisores hasta la raiz del número, en vez de su mitad. Esto es aún más óptimo. Por ejemplo el 29, pruebas divisores sólo hasta el 5. La lógica es que si no ha aparecido ningún divisor antes de la raiz no aparecerá ya después, pues si hubiera un divisor mayor que la raiz, el cociente sería menor (y habría aparecido antes).
    – abulafia
    Commented el 17 oct. 2020 a las 21:36
  • Es muy cierto, hago una comprobación final y si es correcto edito mi respuesta.
    – RuDaHee
    Commented el 17 oct. 2020 a las 21:38
  • 1
    Gracias a @rudahee, me has ayudado mucho, el programa funciona correctamente. Un saludo
    – jesusdaza
    Commented el 17 oct. 2020 a las 21:49

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.