Plus petit diviseur

Ce que tu notes $d_n$ se note en réalité $P^-(n)$ ou $p(n)$.

Je n'ai pas connaissance d'une telle estimation dans la littérature, donc on va la faire ici :

$$\sum_{2 \leqslant n \leqslant x} \pi(p(n)) = \sum_{p \leqslant x} \pi(p) \sum_{\substack{n \leqslant x \\ p(n) = p}} 1 = \sum_{p \leqslant x} \pi(p) \sum_{\substack{k \leqslant x/p \\ p(k) > p}} 1 = \sum_{p \leqslant x} \pi(p) + \sum_{p \leqslant x} \pi(p) \Phi \left( \frac{x}{p},p \right) = \sum_{p \leqslant x} \pi(p) + \sum_{p \leqslant \sqrt{x}} \pi(p) \Phi \left( \frac{x}{p},p \right)$$
où $\Phi(x,y)$ est la fonction de compte des entiers $2 \leqslant n \leqslant x$ tels que $p(n) > y$ (notation officielle, là aussi), et où l'on a utilisé le fait que $\Phi(x,y)=0$ si $y > x$ à la dernière étape. Les méthodes de crible donnent, si $2 \leqslant y \leqslant x$
$$\Phi(x,y) \ll \frac{x}{\log y}.$$
On en déduit que la $2$nde somme n'excède pas
$$\ll x \sum_{p \leqslant \sqrt{x}} \frac{\pi(p)}{p \log p} \ll x \sum_{p \leqslant \sqrt{x}} \frac{1}{\log^2 p} \ll \frac{x^{3/2}}{(\log x)^3}$$
et donc
$$\sum_{2 \leqslant n \leqslant x} \pi(p(n)) = \sum_{p \leqslant x} \pi(p) + O \left( \frac{x^{3/2}}{(\log x)^3} \right) = \sum_{p \leqslant x} \frac{p}{\log p} + O \left( \frac{x^{2}}{(\log x)^3} \right) = \frac{1}{2} \left( \frac{x}{\log x} \right)^2 + O \left( \frac{x^{2}}{(\log x)^3} \right).$$

Combien de divisions ton programme effectue pour N = 3000. ?

c'est pour ça que ton programme est long, pour vérifier tes 1 000 000 000 de nombres premiers N < 22 801 763 550.

Tu as 371 nombre premiers < 3000. en excluant 3 et 5 avec leur multiples

Comme tu commences à n = 61, tu as au minimum (3000 / 3,75) -13 = 787 impairs (non multiples de 3 ou 5) à tester .
Mais en réalité avec 340 divisions en gros, tu fais le même travail, au lieu de tester 371 * 13 , soit 4873 divisions inutiles ....

voila une idée pour programmer selon le principe d'Ératosthène modulo 30, tu vas comprendre pourquoi on a que 340 sauts à faire.

lorsque tu as tester tes entiers impairs avec P = 7 , tu marque ses multiples d'un 0, donc inutile d'y revenir dessus avec les autres premiers de base >7 et < ou = 53

7 ne fera que 800 / (7*8) = 114 divisions , car il teste uniquement 8 entiers par bloc de 56.

Ensuite 11 fera de même ( les restants / (11*8)) donc à nouveau 8 entiers par bloc de 88 ..sans tester les 0 = multiples de 7, soit 70 divisions , donc 70 zéros de plus à ne pas tester par P = 13 ....et ainsi de suite....Le crible accélère au fur et à mesure...
A la fin, il ne te reste que les nombres premiers qui ne peuvent être marqué zéro...

Voila ce que cela donne : j'ai marqué en rouge tous les multiple de 7 , il y en a 8 par bloc de 56, sans avoir besoin de faire de divisions, selon le principe Ératosthène ...
Tu commences du carré de 7 et tu marques ses multiples en utilisant sa table de saut {(12) ,7,4,7,4,7,12,3} ,12) le carré de 7 commence à 12 nombres de P = 7. et tu réitères jusqu'à la fin . Ensuite par colonne les multiples de 7 , se trouvent 7 ligne en dessous.
Autrement dit, tu cribles ou testes modulo 7*30 par colonne ; donc tu vas tester modulo P*30 pour l'ensemble de ces 800 entiers .

le seul hic c'est la mémoire que prend l'écriture de tous ses entiers...< 22 801 763 550.

C'est pour cela que mes algorithme modulo 30 fonctionnent par famille. Donc avec une limite $N$ 8 fois plus grande.
Mais j'utilise une autre méthode, que tu as pu voir avec le code Python d'Ératosthène mod 30.

P = 7 : {(12) ,7 , 4 , 7 , 4, 7 , 12 , 3} ,12)
+ D... : {(48),32,16,32,16,32,48,16 }
P = 37 :{(60),39,20,39,20,39,60,19)60} je remet 60 à la fin après l'accolade, car on part toujours du carré de P , donc de 37 dans cet exemple.
Quand tu ré-indexes la table pour P = 37 c'est simple , tu rajoutes les 8 valeurs de la table D aux 8 valeurs de la table de P =7

Cela te permet de vérifier que la variante d'Ératosthène modulo 30, n'a pas d'erreur...;-) tous les carrés de P sont indiqués , soit colonne 1 mod 30 , ou colonne 19

Bonne soirée.

Pour reformuler l'optimisation proposée par LEG,
je veux tester tous les nombres entre 6000 et 47999.
Version archi-basique : je regardre 6000 , puis 6001, puis 6002 etc.
Pour chacun, je teste s'il est divisible par 2, puis par 3, puis par 5, puis par 7 etc etc.
Pour tous les nombres, on va commencer par tester la divisibilité par 2... gros gâchis.
Testons uniquement les nombres impairs (6001, 6003, 6005 etc etc) et on ne teste pas si ce nombre est divisible par 2. On vient d'économiser 42000 divisions.

Version un peu plus évoluée : on va faire la même chose, mais en évitant les multiples de 3.
On sait d'entrée que parmi les impairs, ceux qui sont de la forme 6003+6k sont des multiples de 3. et ceux qui sont de la forme 6001+6k ou 6005+6k ne sont pas des multiples de 3. On peut donc tester uniquement les nombres de la forme 6001+6k ou 6005+6k, et on n'a plus besoin de tester la divisibilité par 3. On vient d'économiser encore 21000 divisions.

Pareil, en évitant les multiples de 5. On a donc un cycle de 2x3x5=30 et il suffit de regarder les nombres de la forme 6000+30k+b, avec b=1,7,11,13,17,19,23 ou 29 . Et plus la peine de tester si notre nombre est multiple de 5, par construction, on a éliminé les multiples de 5 du périmètre.

On pourrait aussi éviter tous les multiples de 7, on aurait un cycle de 210 , en regardant les nombres de la forme 6000+210k+b, avec b=1,11,13,17 ... (48 familles à tester)

etc etc
La version de Leg est faite pour éviter les multiples de 2, 3 et 5, et il y a donc 8 familles à tester.

@zephir au moins tu t'es fait plaisir à les extraire...
Le site propose une grosse base de donnée de nombres premiers répertoriés, ce qui permet d'obtenir un résultat immédiat, mais malheureusement dans ton cas il t'a fallu faire chauffer ta machine...

La méthode que je t'ai proposée le permet beaucoup plus facilement pour le premier milliard de premiers...
ainsi que le dernier fichier que j'ai posté, programmé en c++... ou sûrement avec en langage Fortran.

Bon courage pour ta suite.
Cordialement.

[Les points de suspension son au nombre de trois, et jamais d'espace avant une virgule ou un point. AD]