Effettivamente l'algoritmo è estremamente migliorabile, aggiungendo il controllo solo sui dispari.

In via teorica è possibile testare solo sui numeri primi precedenti la radice... ma qui rientriamo nel caso del cane che si morde la coda: come estraiamo tutti i primi minori della radice? Mi serve un algoritmo per testare la primalità... :gren:

In realtà esiste un algoritmo polinomiale, che è stato realizzato pochi anni fa... si chiama AKS (dalle iniziali dei suoi tre inventori), ma non mi ci metto nemmeno a capirlo...


Ciao.