volver

Largest Prime Factor

The prime factors of $13195$ are $5,7,13$ and $29$.

What is the largest prime factor of the number $600851475143$?

---

Para calcular el primo mas grande podemos seguir este algoritmo:

• $n\leftarrow$ Numero del que queremos el primo mas grande
• $i\leftarrow 2$
• Mientras $i^2<n$ hacer:
  • Mientras $n\equiv 0(modi)$ hacer:
    • $n\leftarrow n/i$
  • Fin bucle
  • $i\leftarrow i+1$
• Fin bucle
• Devolver $n$

Por ejemplo:

$n=123$

Empezamos, $i=2$, entramos en el primer bucle y vemos que $i$ no divide a $n$, por lo que no entramos en el segundo bucle y $i=3$, seguimos en el bucle y como el $3$ si que divide $123$, dividimos, $n$ pasa a ser $41$. El 41 es primo, por lo que $i$ pasa a ser $4,5$ en los siguientes pasos por el bucle sin que ningún número lo divida. Cuando $i=6$, entonces $i^2=64>=41$, por lo que salimos del bucle y devolvemos el $41$.

En python:

def max_prime(n):
    i=2
    while i*i<n:
        while n%i==0:
            n=n//i
        i+=1
    return n

max_prime(600851475143)