Calcolare numeri primi molto grandi

Question

Ciao a tutti, ho finito il secondo ed il terzo homework e adesso mi manca il primo, solo che ho un problema.

Non riesco a trovare un buone idee per calcolare numeri primi molto grandi, riesco a trovare quelli piu' piccoli ma quando mi trovo 26237927(numero primo) non so bene come comportarmi, l'approccio che mi e' venuto in mente e' quello di vedere se e' primo tramite divisioni successive ma mi sembra molto inefficiente, vorrei se possibile che qualcuno di voi mi consigliasse qualche algoritmo...

ps: non chiedo che condividiate il vostro codice, vorrei solo sapere qualche teoria matematica  e/o qualche buona idea da implementare

Answer 1

Ciao, come consigliato in un'altra domanda, prova a pensare alla radice quadrata del numero da cui ricavare i divisori! Ti faccio solamente notare che, per esempio il numero 15 è divisibile per 3, però anche 5=15/3 è un divisore di 15! Quindi trovando un divisore in realtà ne trovi ben due.

Answer 2

Ciao!

Per farti ragionare ti posso solo consigliare che devi agire attraverso un ragionamento matematico/logico, non meccanico!
Non esiste alcuna teoria e niente, ma esistono dei ragionamenti per poter approcciarsi a tali problemi!

Ora non posso consigliarti oltre, scusami, perché andrei a dirti come la maggior parte di noi ha ragionato e non sarebbe giusto nei confronti di chi ha "sudato" per arrivare a tale soluzione..
- Francesco Pio Scognamiglio

Comments

Sante parole!

Answer 3

Ciao!
La risposta è già stata data qui

Answer 4

Per trovare tutti i numeri primi inferiori ad un certo numero puoi lavorare allo sviluppo di una funzione che implementi il "Crivello di Eratostene" (trovi spiegazioni ed esempi pratici su internet), ma non credo sarebbe la soluzione più rapida ed immediata, anche se valida, per il primo esercizio; appena completato ciò che ti manca  consiglio comunque di vederti il Crivello tanto per "cultura generale"