Compter les premiers

Fiche dév Ens Sup - Recherche
  • Création ou MAJ importante : 26/11/08
  • Correction mineure : 18/08/09
Mots-clés

Compter les premiers : sommations portant sur les nombres premiers inférieurs à une borne x

Ce logiciel a été développé (ou est en cours de développement) dans la communauté de l'Enseignement Supérieur et de la Recherche. Son état peut être variable (cf champs ci-dessous) donc sans garantie de bon fonctionnement.
  • Site web
  • Système : UNIX-like
  • Etat : en développement
  • Concepteur(s) : Marc Deleglise
  • Contact concepteur(s) : marc.deleglise@univ-lyon1.fr
  • Laboratoire(s), service(s)... : ICJ

 

Fonctionnalités générales du logiciel

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) .

Publications liées au logiciel
  • Computing pi(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method. M. Deleglise, J. Rivat Mathematics of Computation 1996 Vol 65, Number 213, pp-235-245
  • Counting primes in residue classes. M. Deleglise, P. Dusart et Xavier Roblot. Math. Comp. 2004, vol. 73 : 247, pp. 1565-1575.