Algoritmi - Metdodo veloce per trovare numeri primi

Forum - Algoritmi - Metdodo veloce per trovare numeri primi

XBarboX (Member)
Guru

Messaggi: 945
Iscritto: 31/12/2008

Postato alle 15:21
Mercoledì, 29/06/2011

ciao a tutti,
ho bisogno di risolvere questo problema:

Codice sorgente - presumibilmente Delphi

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?

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 17:28
Mercoledì, 29/06/2011

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

http://www.google.com/search?q=++++The+prime+factors+of+13 ...

Ultima modifica effettuata da pierotofy il 29/06/2011 alle 17:32

il mio scopo era creare un programma che lo risolvesse, non trovare la risposta. Comunque la soluzione si trova qui: http://projecteuler.net/project/resources/003_96c8248cc19fc7807cdacab7c7e4b3b2/003_overview.pdf - XBarboX - 29/06/11 17:38

oltre alle risposte ho trovato tanti programmi che lo risolvono... c'è ne sarà uno che ti soddisfa oppure stai cercando di scoprire qualche metodo più veloce che non è stato ancora provato? - pierotofy - 29/06/11 20:53

Bha diciamo che avendo fretta non ho letto le altre soluzioni e dato che sono riuscito a risolverlo non ho neanche controllato di nuovo la soluzione ottimale. Se poi per caso riguardo il codice e mi vengono dei dubbi di sicuro li postesò qui sul forum. Comunque grazie mille - XBarboX - 29/06/11 21:01

Il mio blog: https://piero.dev