by Il vaut mieux a mon avis tester la parite en premier et utiliser une boucle for qu'une boucle while dans un cas comme celui-ci, ca evite d'oublier d'incrementer la variable d'indice, donc en Python mettre for k in range(3,n,2): puis utiliser un test et un return: if k*k>n: return 1
En C, tout se fait dans l'instruction for.
- Code: Select all
// pour n<2^32
if (n<2) return 0;
if (n%2==0) return n==2;
for (unsigned k=3;k*k<=n;k+=2){
if (n%k==0) return 0;
}
return 1;
L'astuce d'ajouter 2*k+1 a une variable pour tester ne sert pas reellement ici, car on ne va pas tester de tres grandes valeurs de k, ca prendrait trop de temps, disons pas plus que 2^16 en pratique, donc k*k va se faire en multipliant des entiers 32 bits, ce qui prend 1 cycle sur les CPU modernes.
Ce qui prend le plus de temps, c'est le calcul du reste euclidien.
Et si on veut optimiser encore plus, on utilise une table de nombres premiers, par exemple <=10000 pour eviter de tester avec des entiers non premiers.
