#007 Primo 10001 — Euler Lab

¿Qué es un número primo?

Un número primo es aquel que solo es divisible por 1 y por sí mismo. El 1 no se considera primo.

1º 2

2º 3

3º 5

4º 7

5º 11

6º 13

7º 17

8º 19

9º 23

10º 29

¿Cómo verificar si n es primo?

1

Si n < 2, no es primo

Por definición, 0, 1 y negativos no son primos

2

Buscar divisores entre 2 y n-1

Si encontramos alguno, n no es primo

3

Optimización: solo hasta √n

Si n tiene un divisor > √n, también tiene uno < √n

Si d divide a n y d > \sqrtn \to n/d < \sqrtn Solo necesitamos probar divisores hasta \sqrtn

Conceptos clave

💜 Primos ➗ Divisibilidad √ Raíz cuadrada 🔢 Conteo

La estrategia

Contar primos uno a uno hasta llegar al 10.001º. Para cada número, verificamos si es primo.

Optimización básica: Después del 2, solo los impares pueden ser primos. Ahorramos la mitad de las comprobaciones.

Variante A: while True + break

Bucle infinito que rompe cuando encontramos el primo 10.001.

Python

def es_primo(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # Solo probar impares hasta √n
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i = i + 2
    return True

contador = 0                # Cuántos primos hemos encontrado
n = 1                       # Número actual a probar

while True:
    n = n + 1
    if es_primo(n):
        contador = contador + 1
        if contador == 10001:
            break

print(n)

Pulsa "Ejecutar" para ver el resultado

Variante B: while con condición

La condición de salida va en el while.

Python

def es_primo(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

contador = 0
n = 1

while contador < 10001:
    n += 1
    if es_primo(n):
        contador += 1

print(n)

Pulsa "Ejecutar" para ver el resultado

Variante C: saltando pares

Contamos el 2 aparte y luego solo probamos impares.

Python

def es_primo(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

# El 2 es el primer primo
contador = 1
n = 1  # Empezaremos con 3

while contador < 10001:
    n += 2              # Solo impares: 3, 5, 7, 9...
    if es_primo(n):
        contador += 1

print(n)

Pulsa "Ejecutar" para ver el resultado

¿Cuál elegir?

Variante	Candidatos probados	Ventaja
A: while True	~104.743	Explícita
B: while condición	~104.743	Sin break
C: solo impares	~52.372	2× más rápida

Resultado (las tres variantes) 104743

Conceptos clave

1

`i * i <= n`

Equivale a i <= √n pero sin calcular raíz (más rápido).

2

`int(n**0.5) + 1`

n**0.5 es √n. int() trunca. +1 incluye el límite.

3

`range(3, limit, 2)`

El tercer argumento es el paso. 2 genera 3, 5, 7, 9... (solo impares).

4

`return True/False`

La función devuelve un booleano. Podemos usarlo directamente en if.

Conceptos de Python aprendidos

🎯 Funciones con return ✓ Booleanos 🔢 range con paso ** Exponenciación

Generador infinito de primos

Creamos un generador que produce primos indefinidamente. Luego tomamos el 10.001º.

Python

def es_primo(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    return all(n % i != 0 for i in range(3, int(n**0.5) + 1, 2))

def generador_primos():
    """Genera primos infinitamente"""
    yield 2
    n = 3
    while True:
        if es_primo(n):
            yield n
        n += 2

# Tomar el primo 10001
from itertools import islice
primo_10001 = next(islice(generador_primos(), 10000, 10001))

print(primo_10001)

Pulsa "Ejecutar" para ver el resultado

Desglose

1

`all(n % i != 0 for i in ...)`

all() devuelve True si todas las condiciones son verdaderas. Verifica que ningún i divide a n.

2

`yield`

Convierte la función en generador. Produce un valor y pausa hasta que se pida el siguiente.

3

`islice(gen, 10000, 10001)`

De itertools. Toma elementos del índice 10000 al 10001 (solo uno).

4

`next(...)`

Obtiene el siguiente elemento del iterador. Como islice da uno solo, ese es nuestro resultado.

Resultado 104743

Conceptos aprendidos

🌊 yield (generadores) ✓ all() 🔧 itertools.islice ➡️ next()

Criba de Eratóstenes

Para encontrar muchos primos, es más eficiente generar todos los primos hasta un límite con la Criba de Eratóstenes.

Visualización: primos hasta 50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Tachamos múltiplos de 2, luego de 3, de 5... Los que quedan son primos.

?

¿Hasta dónde buscar?

El primo 10.001º es ~104.743. Usamos 150.000 como límite seguro (por el teorema de los números primos).

Python

def criba_eratostenes(limite):
    """Genera todos los primos hasta limite usando la Criba"""
    # True = potencialmente primo, False = compuesto
    es_primo = [True] * (limite + 1)
    es_primo[0] = es_primo[1] = False

    # Para cada número desde 2
    for i in range(2, int(limite**0.5) + 1):
        if es_primo[i]:
            # Tachar todos los múltiplos de i
            for j in range(i*i, limite + 1, i):
                es_primo[j] = False

    # Recoger los primos
    return [i for i in range(limite + 1) if es_primo[i]]

# Generar primos suficientes
primos = criba_eratostenes(150000)

print(f"Generados {len(primos)} primos")
print(f"El primo 10001 es: {primos[10000]}")

Pulsa "Ejecutar" para ver el resultado

Comparativa de rendimiento

Método	Para 10.001 primos	Complejidad
Probar cada n	~1.5 segundos	O(n√p)
Criba	~0.02 segundos	O(n log log n)

Probar cada n ~1.5 segundos

Criba de Eratóstenes ~0.02 segundos

Resultado 104743

Conceptos aprendidos

🔢 Criba de Eratóstenes 📋 Listas booleanas ⚡ O(n log log n) 🎯 List comprehension

¿Qué es un número primo?

¿Cómo verificar si n es primo?

Si n < 2, no es primo

Buscar divisores entre 2 y n-1

Optimización: solo hasta √n

Conceptos clave

La estrategia

Variante A: while True + break

Variante B: while con condición

Variante C: saltando pares

¿Cuál elegir?

Conceptos clave

i * i <= n

int(n**0.5) + 1

range(3, limit, 2)

return True/False

Conceptos de Python aprendidos

Generador infinito de primos

Desglose

all(n % i != 0 for i in ...)

yield

islice(gen, 10000, 10001)

next(...)

Conceptos aprendidos

Criba de Eratóstenes

Visualización: primos hasta 50

¿Hasta dónde buscar?

Comparativa de rendimiento

Conceptos aprendidos

Prueba con otro índice

`i * i <= n`

`int(n**0.5) + 1`

`range(3, limit, 2)`

`return True/False`

`all(n % i != 0 for i in ...)`

`yield`

`islice(gen, 10000, 10001)`

`next(...)`