Optimisations en théorie des nombres pour le traitement algorithmique
Crible linéaire
L'objectif est de déterminer tous les nombres premiers jusqu'à une borne \(n\), avec \(n \le 10^8\). Le crible d'Ératosthène classique a une complexité de \(O(n \ln \ln n)\), car il marque les multiples de chaque nombre premier à plusieurs reprises. Pour une efficacité optimale, on utilise un crible linéaire où chaque nombre com ...
Publié le 15 juin à 17h41