Crible d'Ératosthène variante sans doublons

Bonjour
citation Fly7

En ayant confiance en ce crible et en connaissant la progression du nombre de solutions pour chaque multiples de premier.
Il est possible d’écrire un algorithme peut être plus performant que le crible d'Ératosthène.

Déjà: comment tu vas faire pour éviter les doublons$ > 3*10^{12}$ des nombres premiers $P\leqslant\sqrt{n}$(:P)

Prends seulement $n = 30 000$ tu penses aller plus vite que ce qui existe déjà pour le crible d'Ératosthène....:)o

As tu au moins une idée de ce qui existe actuellement, alors que tu est dans l'impossibilité d'écrire ton crible $< 10^9$

Il faut 28 secondes pour calculer le nombre de nombres premiers $P\equiv{1}[30]$ , $< 300 000 000 000$; c'est à dire un peu moins de 4 minutes pour les 8 familles ...limite: $15,3 * 10^{12}$ environ 8h..sur un PC de 8 Go de ram.

Et il y a beaucoup plus rapide , avec le crible de H. A. Helfgott et sa méthode du cercle; quant à sa limite, je pense que lorsque tu auras fini d'écrire ton crible, tu serras à la retraite....

Mais, bon courage....

Fly7 à écrit:

peut être plus performant que le crible d'Ératosthène.

c'est bien toi qui parle de performance ?

pourquoi : Excepté 49, 77 et 91 qui sont passé à travers le crible mais ne sont pas premier. ?

Du moment que ton crible ne les a pas écrit comme multiple de P, et ben ils sont premiers...

donc je pose n = 300, limite du crible ...

on laisse tomber les multiples de 2,3 et 5 pour faciliter..ok ?

ton crible ou toi va donc écrire à partir de ton produit $2*3*5*7 = 210$ soit, modulo 210

$210n+(±7 ou ±49 ou ±77 ou ±91)$ comment tu vas écrire les multiples de $P\leqslant \sqrt{300}$ autre que ceux de $P=7$ avec ton prochain produit $210*11=2310$
2310n + ou -11 .....etc ?
si ton algorithme est incapable de se construire lui même faute d'instructions, avec $2310n$ ....? d'après tes dires.

à part les écrire toi même et modulo P ....:)o

Ou encore modulo $P*30$ = (30*11) - 11.....etc.... (30*13) -13 ; (30*17) -17.....
c'est et ce sera toujours Ératosthène en plus compliqué et moins performant...Non ?
Par ce que je suppose quand même, que tu ne vas pas partir de 2310n -11........pour revenir à 121 ...etc ...etc

Il est inutile d'aller au delà du crible multiples de 5 et d' aller au delà de n =1 pour le crible multiple de 5.

pour limite N = 49. c'est bien......

Et pour aller jusqu'à $N = 3 000 000 0001$ ? tu n'as besoins que de: 7, 49,77 et 91 pour calculer les multiples de 7 avec $210n$ valeur de $n$ ? temps de la performance de ton crible ? :

("parce que avec 7 c'est suffisant pour barrer les multiples de 7 sans faire des additions, soustractions, multiplications...inutiles. Il suffit de programmer par pas de 7 depuis $7\rightarrow {N}$ ")

Puis pour $2310n$ avec 11 ,121 ......$(11*P_k)$ valeur de $P_k$ ; valeur de $n$ et uniquement les 32 multiples de 11 ?

Car écrire tous les produits à coups d'additions, soustractions et multiplications "inutiles" tu penses que c'est toujours plus performant que d'écrire les entiers naturels > 0 jusqu'à $N$ puis de barrer par pas de $P_k$$<\sqrt{N}$
même en te limitant aux impairs , voir sans les multiples de 3 et 5....et même 7...en utilisant le modulo 210.etc etc

Bonjour
Ce que j'ai voulu te faire remarquer , c'est qu'il est inutile d'écrire les multiples de 2,3 et 5.
Donc Ératosthène est limité aux entiers impairs non multiples de 2,3 et 5 , et ton procédé n'est pas rapide , on n'a nul besoins d'écrire tous les multiples de $P_k > 5$ , pour cribler . Y compris pour cribler de N à 2N avec une limite N fixée....

On part soit du carré de $P_k$ soit du produit de : $P_k * P_n = J$ avec $P_k$ appartenant à {11,13,17,19,23,29,31, et 37} et $P_n$ l'ensemble des nombres premiers $P\leqslant\sqrt{N}$ où $N$ est la limite à cribler.
("donc comme tu peux le constater on n'a même pas besoins d'écrire les entiers impairs multiples de 7.....mais ce n'est pas ce qui va faire gagner du temps..")

ensuite tu travailles modulo $P_n*30$ .

Exemple si je veux supprimer les multiples de $P_n = 11$ je part de $11^2$, modulo $330$; puis du produit $11*13$ + modulo $(13*30)$ :

(11*13) + modulo 390.......>N
(11*17) + modulo 510.......>N
etc
13*13 + mod 390....>N
13*17 + mod 510...>N

Mais c'est long et peu performant ...D'ailleurs quelque soit le crible d'Ératosthène modifié...
Par exemple sans les multiples de 7, avec modulo 210;

11*13 + modulo 2310 ....>N
11*13 + modulo 2730 ....>N
etc etc ...mais c'est toujours long....Ce n'est pas parce que tu sauteras, ou évitera les nombres déjà marqué par des opérations de soustraction et additions inutiles, que tu gagneras du temps car tu seras limité en mémoire de stockage sans pour autant aller plus vites....

On va déjà plus vite modulo $P_n$ par famille arithmétique de raison 30.
$P_k = 7_1,11_2,13_3,17_4,19_5,23_6,29_7,31_8 $

le programme construit un tableau de 1 jusqu'à $N//30$ ; puis crible en partant du produit $P_{k1} * P_n = J$ modulo $P_n$ jusqu'à $N$.
soit il barre les 1 ou change le signe du Bit, ou encore remplace le 1 par 0.

Puis tu réitères avec $P_{k1} * P_{n+1} = J$.
une fois tous les $P_n$ utilisé avec $P_{k1}$ ; tu récidives avec $P_{k2} * P_n $
etc etc ....à la fin tu comptabilises les 1.

fam 7 = 7,37,67,97, ....N//30
$[1,1,1,1,.....1 = N//30]$
$7*31 = J = 217 \equiv {7}[30]$ , puis calcul de l'index de départ $J//30 = 7$ tu pars du 7ème 1 = 217; car tu comptes de: 0,1.2.3.4....7 qui est bien le produit $7*30 + 7 = 217$.
donc tu cribles part pas de $7\rightarrow\:N$

extrait du crible :
Pour N = 6000 mds, nombre de premiers 13 mod 30; 26 422 717 616 en 1 677,97 secondes
Pour N = 7500 mds, nombre de premiers 13 mod 30; 32 770 358 492 en 2142,95 secondes

tu vois que même, si on utilisait une méthode encore plus rapide on sera toujours limité par la limite N. la mémoire de stockage etc ....etc...
Bon courage