Aller au contenu

Tracer la fonction π(x)

Suite à une nouvelle question sur tex.stackexchange.com, poursuivons sur la lancée des nombres premiers et demandons-nous à présent comme tracer la fonction \(\pi(x)\) qui, lorsque \(x\) est entier, représente le nombre d’entiers premiers inférieurs ou égaux à \(x\).

Avant d’envisager tout tracé, il faut élaborer un test qui décide si un nombre est premier ou pas. Une multitude de tests existent, dont la complexité asymptotique va de l’exponentielle au polynomial. Nous n’irons pas bien loin dans les valeurs de \(x\), il est donc inutile de programmer très élaboré. Une approche naïve suffira amplement.

Tester si un entier est premier

Cette approche s’appuie sur le fait qu’un nombre premier est de la forme \(6k-1\) ou \(6k+1\). Il suffit donc de tester si le nombre \(x\) est successivement divisible par \(6k-1\) ou \(6k+1\) jusqu’à ce que \(6k+1>\sqrt{x}\).

En pseudo code (vu sur wikipedia), cela donne :

Pour simplifier encore davantage, nous allons considérer que le nombre à tester \(x\) est impair puisque ce sera le cas dans la boucle itérant sur \(x\) pour tracer la fonction \(\pi(x)\).

La traduction de cet algorithme en TeX est aisée sinon triviale. Elle suppose tout de même qu’une macro \modulo{<x>}{<y>}, purement développable, renvoie le reste de la division de <x> par <y>. Cette macro fera appel à la macro \truncdiv pour évaluer avec \numexpr une division donc le quotient est la troncature.

Retenons au passage que 1 est considéré à tort comme étant premier par ce test.

Tracer la fonction π(x)

Il ne reste plus qu’à cumuler les nombres premiers rencontrés jusqu’alors (en partant de -1 pour compenser le faux positif pour 1). Cette variable cumulative sera un simple compteur. La mise en œuvre, qui passe par \graphzone, une boucle \for dont le pas est 2 (pour sauter les nombres pairs), est triviale.

Le tracé est vraiment rapide, moins d’une seconde sur mon PC qui n’est pourtant pas un foudre de guerre.

pi_x_

 

Laisser un commentaire