Algoritmi - Metdodo veloce per trovare numeri primi

ciao a tutti,
ho bisogno di risolvere questo problema:

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

What is the largest prime factor of the number 600851475143 ?

Ho già fatto una soluzione ma ci mette troppo tempo.
Vorrei sapere come capire in fretta se un numero è primo o meno.
Mi è venuto in mente il crivello di Eratostene ma visto che 600851475143 sborda di molto il limite di un vettore di bool non ho buone idee.
Consigli?

E' un problema che è stato risolto diverse volte... proverei a guardare su Google:

google.com/…