Algoritmia - Numeros primos

Numeros primos

Publicado por Christian (1 intervención) el 04/10/2004 22:14:21

Hola, alguien conoce el algoritmo para obtener numeros primos? gracias

Valora esta pregunta

Me gusta: Está pregunta es útil y esta clara

No me gusta: Está pregunta no esta clara o no es útil

Responder

Criba de Eratóstenes para generar números primos

Publicado por Alejandro (307 intervenciones) el 01/03/2024 20:28:47

Sí, Christian, existen varios algoritmos para encontrar números primos. Uno de los más comunes es la "criba de Eratóstenes", que es un método simple y eficiente para generar todos los números primos hasta un cierto límite.

Aquí hay una descripción básica del algoritmo:

1. Crear una lista de números del 2 al límite que deseas.
2. Comenzar con el primer número no marcado (que es 2) y marcar todos sus múltiplos como compuestos.
3. Moverte al siguiente número no marcado y repetir el proceso.
4. Repetir hasta que hayas examinado todos los números en tu lista. Los números no marcados en este punto son primos.

Aquí tienes una implementación simple en Python para encontrar todos los números primos hasta un límite dado utilizando la criba de Eratóstenes:

def criba_eratostenes(limite):

    # Inicializar una lista de booleanos para marcar los números compuestos

    es_primo = [True] * (limite + 1)

    es_primo[0] = es_primo[1] = False  # 0 y 1 no son primos

    # Marcar múltiplos como compuestos

    for num in range(2, int(limite**0.5) + 1):

        if es_primo[num]:

            for multiple in range(num**2, limite + 1, num):

                es_primo[multiple] = False

    # Obtener la lista de números primos

    primos = [num for num in range(2, limite + 1) if es_primo[num]]

    return primos

# Ejemplo de uso

limite = 50

print("Números primos hasta", limite, ":", criba_eratostenes(limite))

Este código te dará una lista de números primos hasta el límite que determines. Para aplicaciones más grandes, hay algoritmos más avanzados, como el algoritmo de prueba de primalidad de Miller-Rabin, pero la criba de Eratóstenes es un buen punto de partida.

Valora esta respuesta

Me gusta: Está respuesta es útil y esta clara

No me gusta: Está respuesta no esta clara o no es útil

Comentar