Oui, oui.
Autant pour moi. J'avais oublié le temps nécessair à la division.
Je n'avais compté que le nb de test à faire qui lui est en racine(n).
Par contre c'est quoi cet algo en log(n)^2 pour une division?
Je connaissais juste qq chose en O(n*log(n)) (je crois) via une FTT (transformé de fourier rapide).
Sinon, je pense que Mous il mouline un peu dans la choucroute ce matin ;-)
Pour factoriser N, un algo naif reviens à essayer de le diviser par tous les nombres inférieurs à sa racine (pour aller plus vite on vire les multiples de 2 et de 5).
Ça sert à rien avant de faire chaque test de voir si le n par lequel on va essayer de diviser est premier ou pas.
[^] # Re: Un peu de maths [correction]
Posté par Cédric Foll . En réponse à la dépêche Le RSA en danger. Évalué à 3.
Autant pour moi. J'avais oublié le temps nécessair à la division.
Je n'avais compté que le nb de test à faire qui lui est en racine(n).
Par contre c'est quoi cet algo en log(n)^2 pour une division?
Je connaissais juste qq chose en O(n*log(n)) (je crois) via une FTT (transformé de fourier rapide).
Sinon, je pense que Mous il mouline un peu dans la choucroute ce matin ;-)
Pour factoriser N, un algo naif reviens à essayer de le diviser par tous les nombres inférieurs à sa racine (pour aller plus vite on vire les multiples de 2 et de 5).
Ça sert à rien avant de faire chaque test de voir si le n par lequel on va essayer de diviser est premier ou pas.