Compter les premiers
Pour le moment 4 programmes sont disponibles :
- Le programme pi calcule pi(x), le nombre des entiers premiers <= x.
Le temps de calcul est O(x^(2/3)/ln^2(x)) (en comptant pour 1
toutes les opérations arithmétiques, ce qui n'est pas tout
à fait vrai puisque les entiers sont codes en utilisant gmp).
En pratique on peut calculer pi(x) pour x <= 10^21 en 8 jours de calcul. - Le programme sumprime calcule la somme des premiers <= x
aussi en temps O(x^(2/3)/ln^2(x)). - Le programme nemprime retourne le n ième nombre premier.
Le temps de calcul est à peu prés le même que le temps
de calcul de pi(x) avec x=n * log(n). - programme invsumprime
retourne le plus grand nombre premier p tel
que la somme des premiers <= p ne dépasse pas x
Ces programmes sont tous dérivés du programme de calcul de pi(x)
présenté dans
Computing pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method. (voir publications)
Compter les nombres premiers jusqu'à x c'est sommer les valeurs de la fonction
complètement multiplicative f(n) = 1 sur tous les n <= x qui sont premiers.
La méthode s'adapte au calcul dela somme des f(p) pour tous les premiers
jusqu'à x pourvu que f soit une fonction complètement multiplicative
et que la fonction sommatoire F(x) = somme des f(n) pour n <= x
soit facile à calculer.
Choisisssant la fonction f(n) = n, on calcule ainsi la somme de tous les nombres
premiers jusqu'à x.
La méthode s'adapte aussi au calcul de la somme des f(p) pour les p
premiers <= x appartenant à une progression arithmétique de la forme
an+b avec a et b premiers entre eux.
Ceci a été fait et publié lorsque f(n)=1 dans
Counting primes in residue classes (voir publications) .