#010 Suma de Primos

1 Entendiendo el Problema

Debemos sumar todos los números primos menores que 2 millones. Un número primo solo es divisible por 1 y por sí mismo.

Ejemplo: Primos menores que 30

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

Suma = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 = 129

148,933

Primos menores que 2M

~7.4%

Densidad de primos

1,999,993

Mayor primo < 2M

Respuesta

142,913,828,922

Límite

n < 2,000,000

2 Fuerza Bruta - 3 Variantes

Probamos cada número y verificamos si es primo mediante división por prueba.

Variante A: while True + break

Test de primalidad básico con break.

Python

# Versión reducida para demo (limite bajo)
LIMIT = 1000  # Cambiar a 2_000_000 para respuesta real

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    divisor = 3
    while True:
        if divisor * divisor > n:
            break
        if n % divisor == 0:
            return False
        divisor += 2

    return True

total = 0
n = 2

while True:
    if n >= LIMIT:
        break

    if is_prime(n):
        total += n

    n += 1

print(f"Suma de primos < {LIMIT}: {total}")

# Para 2,000,000 la respuesta es: 142913828922

// Output aparecerá aquí

Variante B: while condición

Condiciones directas en el while.

Python

LIMIT = 1000

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True

total = 0
n = 2

while n < LIMIT:
    if is_prime(n):
        total += n
    n += 1

print(f"Suma de primos < {LIMIT}: {total}")

// Output aparecerá aquí

Variante C: for range

Usando for con range y optimización √n.

Python

from math import isqrt

LIMIT = 1000

def is_prime(n):
    """Test de primalidad O(√n)."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False

    return True

total = 0

for n in range(2, LIMIT):
    if is_prime(n):
        total += n

print(f"Suma de primos < {LIMIT}: {total}")

// Output aparecerá aquí

Análisis de complejidad

Tiempo

O(n × √n)

n números × √n divisiones cada uno

Espacio

O(1)

Solo variables auxiliares

⚠️ Para n = 2,000,000 esto es muy lento (~minutos). Necesitamos la Criba de Eratóstenes.

3 Enfoque Pythónico

Usando generadores, filter, y comprensiones con la criba básica.

Python

LIMIT = 10_000  # Reducido para demo rápida

def sieve(n):
    """Criba de Eratóstenes pythónica."""
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # Marcar múltiplos como compuestos
            is_prime[i*i::i] = [False] * len(is_prime[i*i::i])

    return is_prime

# Generar primos y sumar
primes = sieve(LIMIT)
result = sum(i for i, is_p in enumerate(primes) if is_p)

print(f"Suma de primos < {LIMIT}: {result}")

# Alternativa con filter + enumerate
primes_list = [i for i, is_p in enumerate(primes) if is_p]
print(f"Cantidad de primos: {len(primes_list)}")
print(f"Primeros 10: {primes_list[:10]}")
print(f"Últimos 5: {primes_list[-5:]}")

// Output aparecerá aquí

Herramientas usadas

is_prime[i*i::i] — Slice con paso para marcar múltiplos
enumerate() — Índices y valores
sum(generator) — Suma perezosa
List comprehension con filtro

El truco del slice

# Marcar múltiplos de 3 desde 9:
# arr[9::3] = [False] * count

# Es equivalente a:
for j in range(9, n, 3):
    arr[j] = False

4 Criba de Eratóstenes Optimizada

La Criba de Eratóstenes es el algoritmo clásico para encontrar todos los primos hasta n. Optimizamos memoria usando solo impares.

Visualización: Criba hasta 100

Primo Compuesto (tachado)

O(n log log n) Complejidad temporal

O(n) \to O(n/2) Memoria (optimizada solo impares)

Python — Criba optimizada

def sum_primes_sieve(limit):
    """
    Suma todos los primos menores que limit usando
    la Criba de Eratóstenes optimizada.

    Optimizaciones:
    1. Solo almacenamos impares (mitad de memoria)
    2. Empezamos a tachar desde p² (los menores ya están tachados)
    3. Solo iteramos hasta √limit
    """
    if limit <= 2:
        return 0

    # Solo impares: índice i representa el número 2i + 1
    # Tamaño: limit // 2
    sieve_size = limit // 2
    is_prime = [True] * sieve_size
    is_prime[0] = False  # 1 no es primo

    # Cribar
    i = 1  # Representa el 3
    while (2 * i + 1) ** 2 < limit:
        if is_prime[i]:
            p = 2 * i + 1  # El primo actual
            # Tachar múltiplos impares de p, empezando en p²
            # p² = (2i+1)² = 4i² + 4i + 1
            # Índice de p²: (p² - 1) // 2 = 2i² + 2i
            start = 2 * i * i + 2 * i
            step = p  # Solo múltiplos impares, así que saltamos 2p/2 = p
            is_prime[start::step] = [False] * len(is_prime[start::step])
        i += 1

    # Sumar: 2 + todos los impares primos
    total = 2
    for i in range(1, sieve_size):
        if is_prime[i]:
            total += 2 * i + 1

    return total

# Ejecutar
LIMIT = 2_000_000
result = sum_primes_sieve(LIMIT)

print(f"Suma de primos < {LIMIT:,}: {result:,}")

# Verificar
print(f"\nVerificación:")
print(f"Esperado: 142,913,828,922")
print(f"Correcto: {result == 142913828922}")

// Output aparecerá aquí

Comparación de rendimiento

Método	Complejidad	Tiempo (n=2M)
Trial division	O(n√n)	~30 segundos
Criba básica	O(n log log n)	~50 ms
Criba optimizada (solo impares)	O(n log log n)	~25 ms

Eratóstenes de Cirene (276-194 a.C.)

Matemático, geógrafo y astrónomo griego. Además de la criba, calculó la circunferencia de la Tierra con notable precisión midiendo sombras en Alejandría y Siena. Su método para encontrar primos sigue siendo uno de los más eficientes para rangos pequeños-medianos.

Summation of Primes

1 Entendiendo el Problema

Ejemplo: Primos menores que 30

2 Fuerza Bruta - 3 Variantes

Variante A: while True + break

Variante B: while condición

Variante C: for range

Análisis de complejidad

3 Enfoque Pythónico

Herramientas usadas

El truco del slice

4 Criba de Eratóstenes Optimizada

Visualización: Criba hasta 100

Comparación de rendimiento

Eratóstenes de Cirene (276-194 a.C.)