Quote:
Originariamente inviato da Ziosilvio
Purtroppo l'algoritmo di Agrawal-Kayal-Saxena opera sì in tempo polinomiale, ma le costanti moltiplicative nascoste sono talmente grandi, che (salvo grossi progressi in teoria dei numeri) all'atto pratico è più veloce l'algoritmo ingenuo!
|
Sinceramente, non conoscevo questo algoritmo! Adesso mi documento...
Io mi riferivo al più semplice crivello di eratostene, dato che deve trovare i numeri primi in un range...