Forum de mathématiques - Bibm@th.net

pas du tout , mais le principe que tu utilises est lourd inutilement d'après ce que je pense comprendre, tu changes la taille de ta roues puis du cribles dans cet intervalle...
déjà que vient faire ce 221 (2*3*5*7 + 11...? pourquoi, que vient faire cette roue de 221...
De plus pour cribler dans l'intervalle de 221, tu n'as besoin que de 7
je ne comprends pas pourquoi tu travailles avec et encore des multiples de 2,3 et 5

si tu pars de ta roue 7*11: 77 les tests  sont 7*7,7*11 point barre donc
tes crans sont {4.2.4.2.4.6.2.6} dont la somme = 30.
7+4; 11+2; 13+4, 17+2, 19+4, 23+6, 29+2, 31+6; on réitère 37+4; 41+2; 43+4; 47+2 filtré par 7*7,49+4; 53+6, 69+2 ;71+6 filtré par 7*11. fin de cette roue;
si j'ai compris ce que fait ton programme.
il faudrait passer ensuite à
{7*11*13} racine carrée =36;  donc tous les premiers P_iappartenant à  [7;31]  et toujours avec une roue à 8 crans....{4.2.4.2.4.6.2.6}? mais je n'en vois pas l'intérêt à première vue...

car il est plus simple de faire ou d'écrire les entiers <(7*11*13) = 1309
ce qui te fais 8 suites arithmétique de raison 30 et tu cribles dans cet intervalle 7;1309. avec les premiers [7;31]
mais en utilisant d'autre pas ou cran..

je part de (7) comment tu barres les multiple de 7 sans calculer les produits < ou = à 1309 par exemple:
7*7,7*11 qui on déjà été trié  et après que fais tu.....?

moi dans un crible d'Eratosthène modifié, je fais ça:

T1 =7;  {12,7,4,7,4,7,12,3,}
je part de 7, je compte 12 et je barre le douzième qui n'est autre que 49, puis je barre le 7ème =77; puis je barre le 4ème = 91..........etc je barre le 3ème qui est le dernier cran ce qui donne 217, et je réitere , 12, 7;4;.....3; je réitère 12,7,....3 jusqu' 1309 et 7 sort du crible pour cet intervalle,

puis je passe à T2 = 11: {18,12,6,11,6,12,18,5}
(11) je barre le 18ème , (qui serra 121), puis le 12ème........puis le 5ème qui est le dernier cran et je réitère, 18,12,....5

et idem pour les premiers [7;31], tu auras criblé sans erreur, les premiers < 1309......non ?

dans ton programme il te faut les 8 tables de 8 termes, la table D pour indexer  {48.32.16.32.16.32.48.16}, à chaque changement de ligne
et par famille

ce qui veut dire que lorsque tu arrives sur P_i > 31, donc 37, tu as changé de ligne tu es dans la famille 30k+7, donc tu indexxe la table ou roue T1 = 7 avec tD
ce qui donne:
  {12, 7, 4 , 7, 4 , 7, 12 , 3,}
+{48.32.16.32.16.32.48.16}

T₃₇= 60;39;20;39;20;39;60;19 dont la somme et bien égale à 37*8;
Ce qui veut dire que la table 37, parcourt 296 entiers par itération, et ne marque que 8 produits par itération et uniquement 1 par colonne ou famille....!

ton programme peut par exemple connaître le format de la table des 8 terme et faire un copier collé par itération, ce qui accélère et évite de compter les nombres, en positionnant bien la table P lignes en dessous de la ligne de départ....etc

Exemple la table 1; T₇: 7 lignes sous la premières ligne qui contient 7 , première colonne. Puisque l'itération se fait toujours même colonne de départ , P_i lignes en dessous.

Pour la table 11, serra 11 lignes en dessous de la ligne de départ 11, et 2ème colonne .
car 11*30+11 = 341 positionné colonne 2, ligne 11, en numérotant ligne 0 la première ligne des 8 premiers P_i : [7;31];

il est évident que dans ce cas, tu peux directement écrire ou représenter les valeurs 30k+1 et 30k+P, dans une taille de tableau à cribler par exemple 100 000 000 000.
sauf la première ligne N° 0 où la tu écris les 8 premiers pour identifier les 8 colonnes [7;31]

Est ce difficile à programmer ?

Zorro est arrivé, car son coffre est rempli de lingots qu'il a tapé à garcia...mais aussi  à capone...et à la famille zitoune..LOL
c'est fort knox son coffre...

moi j'avais trouver 47,09..j donc 48 jours et comme il rembourse des barres pleines. il faut 48j et il aurait taper chez jpp 415 Lingots environ à 1près..
et l'autre 585 lingots remboursé en 67 jour , lui aussi il se ferra taper une barre pleine car jpp le créancier des mafieux, veut des lingots et pas de la poudre...grosse LOL

Bonjour
à vous
en définitive la différence entre les deux cribles nbpremierW32 réside dans le fait que pour cet algorithme P modulo 30, on fixe au départ la taille du tableau des entiers que l'on va cribler, (sans les 2m;3m et 5m)avec le groupe multiplicatif Gm comportant 8 premiers P'[7;31]; et on crible par famille 3k+1 ou 30k +p; soit 8 familles
le lien en exemple pour ce crible nbpremierW32 est :
http://www.cjoint.com/?0AjkYGPspd7

alors que le crible g, lui, il s'alimente tout seul  on peut aussi cribler par famille mais aucun gain de temps, car on est obligé de tester le p' de la famille en question avec tous les [tex]P_i<\sqrt 30k[/tex], donc on crible les 8 familles.

l'avantage, c'est que l'on a pas besoin de créer un tableau fixe que le programme à besoins dans sa mémoire, et il peut dupliquer les lignes des 8 termes, 0 et 1 au fur et à mesure que 30k augmente par pas de 30; mais il serra plus lent par contre il ira plus loin lentement, car il peut utiliser une mémoire externe pour stocker les lignes...[tex]P_i >\sqrt 30k[/tex]

je ne pensais pas qu'entre les mafieux et les voleurs de lingot ils étaient aussi pointus.....LOL
la on a plutôt a faire entre banquiers, et clients qui ne veulent pas rembourser...car c'est flou.....toujours LOL
En définitive il fallait resté anonymes (pour les voleurs,) comme ça pas de problèmes re LOL

Bonjour
@miq
je ne programme pas ce n'est pas du tout mon domaine, ce que je peux te dire c'est que le programme "nbpremier win32" qui a été fait il y a un peu plus d'une dizaine d'année par un étudiant à l'essi de sophia antipolis crible les premiers jusqu'à 450 000 000 par famille [tex]30k + 1[/tex] ou [tex]30k + p[/tex] avec[tex]p, [7;29][/tex] en 4h

celui ci de programme  qui ne fonctionne pas comme "nbpremier win32" et que je n'ai pas encore fait faire, devrait permettre d'aller très loin environ [tex]10^{28}[/tex], car on a pas besoin d'avoir dans la mémoire "virtuelle" une liste de nombre que l'on trie : crible, comme dans Eratosthène, ou "nbpremier win32"

à partir de la racine carrée de [tex]10^{28}[/tex] on n'est plus obligé, de stocker les entiers premiers : [tex]30k - P'[/tex] mais les représenter par 1.
donc on stock que des 1, dans les 8 colonnes qui représentent les 8 familles modulo 30 :[tex]30k + 1[/tex] ou [tex]30k + p[/tex].
donc à partir de cette limite racine carrée on n'a plus besoin de soustraire P' à 30k pour connaître q premier
on teste tout simplement les 8 P'{7;11;13;17;19;23;29;31}
si un des reste [tex]R_i[/tex] de [tex]30k[/tex] par [tex]P_i[/tex] = [tex]P'[/tex]alors 0; sinon 1, puis on stock la lignes:
la ligne 277 dans le fichier Excel:

exemple : avec la ligne des P' relatif à 930.                           
0    1    0    0    1    1    0    0

mais je suppose que l'on ne peut pas garder en mémoire dans le programme tous ces 1 au delà de [tex]\sqrt10^{28}[/tex] pour ne pas saturer, mais de les stocker sur un disque externe de 10

le programme lui n'a besoin que des modulo premiers [tex]P_i <\sqrt10^{28}[/tex] pour calculer les restes de [tex]30k[/tex] par [tex]P_i[/tex]; afin de marquer le ou les 8 [tex]P'[/tex], ligne 277; que l'on stock au fur et à mesure que 30k augmente de 30.

donc la base de donnée première ie; les [tex]P_i[/tex] s'alimente d'elle même et le programme prend dans cette base de donnée, les [tex]P_i <\sqrt10^{28}[/tex] dont il à besoin pour le calcul du reste au fur et à mesure que 30k progresse.

ce qui implique: qu'au fur et à mesure que 30k passe à 30(k+1) les formules de calcul du reste de 30k restent; seul les reste [tex]R_i[/tex] vont changer, et peut être avec un[tex]P_i[/tex] en plus, donc un nouveau reste;

car la racine carrée de [tex]30k[/tex], augmente très peu par rapport à[tex]30(k+1)[/tex].

dans le fichier regarde ce qui se passe en partant de 90 cellule A246, dans le tableau des restes ligne 252 à 259, et tu augmentes de 30 la cellule, jusqu'à 930

il aurait fallu que j'automatise la ligne 266 des 8 P', pour que les P' = [tex]R_i[/tex]passent en rouge ; et donc je ne prend en compte que les P' non marqués, pour la ligne 270 [tex] 30k - P' = q[/tex]
un P' qui est candidat est : [tex]P'\not\equiv30k (mod P_i)[/tex]

Yoshi la ligne 1 à 232, concerne  le criblage de 9540 simplement c'est à dire le nombre de couples q+p = 9540 point barre,
effectivement j'aurais dû le préciser avant que tu n'ouvre ce fichier.
pour en revenir à [tex]\frac{9540}{3,75}[/tex]  c'est le rapport entre les entiers naturels multiple de 2,3 et 5 et les autres de la forme [tex]30k + 1[/tex] ou [tex]30k + P [/tex] avec [tex] P: [7;29][/tex].

pour cribler les premiers, jusqu'à 9540, je n'ai besoin effectivement des premiers P' [7;31] lors que je met 1 ou P [7;29] 1 n'est pas un nombre premier donc les 8 premiers P' [7;31]

pourquoi on limite les P' à [tex]\frac{30k}{2} [/tex] parce que le complémentaire q premier est compris entre [30k/2 ; 30k] tel que :
[tex]q + P' = 30k[/tex]
dans le crible g on utilise les congruences...les multiples de 30 et les premiers [tex]P_i <\sqrt30k [/tex] et ainsi que les 8 P' [7;31]
pourquoi on à besoin que de ces 8 premiers P' c'est pour éviter les doublons < 30k - 31.

les premiers P' compris entre 31 et 30k/2 donnent des doublon q extrait par 30(k-1) donc il faut uniquement les premiers q appartenant à:
[tex][30(k-1) -1 ; 30k -1][/tex]

si [tex]30k - 1[/tex]  est un nombre premier;  tu es bien d'accord que [tex]1 + (30k - 1)[/tex] n'est pas un couple [tex]p' + q[/tex]

si je ne fais pas cela en exemple voila ce qui se passerai:
je crible 60; qui est congru à 4 (mod 7)
[tex]P_i = 7[/tex] donc [tex]R_i = 4[/tex]
les [tex]P' [7;30][/tex]
ce qui donne P'{7,11;13,17;23;29}
on marque les [tex]P' = R_i + n*P_i[/tex]
4+7 =11
11+14 = 25
25 +14 > 30 fin
seul P' = 11  à pour complémentaire q non premier divisible par [tex]P_i[/tex]
on obtient bien:
60 - 7; 60 -13; 60 - 17; 60 - 19 ; 60 -23 , et  60 -29.

je crible 90 qui est congru à 6 (mod 7) ; [tex]\sqrt 90 < 8[/tex]
[tex]P_i = 7[/tex] donc [tex]R_i = 6[/tex]
les [tex]P' [7;45][/tex]
ce qui donne P'{7,11;13,17;23;29;31;37;41;43}
on marque les [tex]P' = R_i + n*P_i[/tex]
6+7 =13
13+14 = 27
27 +14 = 41
41 +14 =  > 45 fin du crible
seul P' = 13 ; et 41 ont pour complémentaire q non premier divisible par [tex]P_i[/tex]
on obtient bien:

90 - 7; 90 -11; 90- 17; 90 - 19 ; 90 -23 ,  90 -29, 90 -31 ; 90 -37 et  90 - 43; sont des doublons
imagine la quantité de doublons pour une limite [tex]P' < 10^{10}[/tex]

donc:
pour le crible rapporte toi ligne 236

re post #12

on est pas dans le système 30k+1 mais 6k+1
donc suivant ton carré de 6 sur 6
A1 = 1 et E1 = 25
49 lui est positionné en C2 car (9-1) * 6 + 1 = 49 c'est pour cela que la cellule A1 est numéroté 0 ensuite tu fais un saut de 5 cellules et de 7cellules...etc et tu obtiens 5*11 et 7*13 à chaque saut le complémentaire de 5 ou 7, augmente de 6.....
tu as bien 55 en D2 et 91 en D3....voila pour l'info sur ce sujet.

re yoshi

1)la racine carrée de n détermine la limite des premiers [tex]P_i[/tex]à utiliser pour cribler et en même temps la limite du crible par exempl [tex]10^28[/tex]...

2) je n'ai besoin pour cribler les premiers [tex]P'[/tex] que ceux appartenant à [tex][7 ; 31][/tex]

pour éviter les doublons, et limiter le nombre d'opération tel que pour un premier [tex]q = 30k - P'[/tex] si et seulement si P' n'est pas congru à 30k modulo [tex]P_i[/tex], ce qui est triviale

3) pour éviter d'avoir à répéter les divisions de 30k par [tex]P_i[/tex], j'utilise le principe Eratosthène pour le petit tableau ligne :252 à 256 du fichier
a)
il me faut quand même les 8 premiers restes [tex]R_i[/tex] de [tex]30k[/tex] par [tex]p_i[/tex] avec [tex]P_i ;[7;31][/tex]
mais ensuite j'utilise le principe d'Eratosthène
Pour [tex]P_i = 7[/tex] et [tex]R_i = 6[/tex] dans le cas de [tex]30k= 930[/tex] il me faut bien vérifier qu'aucun des 8 [tex]P'\not\equiv930 [P_i][/tex] c'est à dire que [tex]P'[/tex] appartenant à[tex][7;31] \not\equiv R_i {(mod P_i)} [/tex] donc je remplace dans le petit tableau
par la formule équivalente et qui m'évite les division[tex]R_i + n * 7[/tex] infér ou = à 31 pour cet exemple; et ce, pour les 8 premiers modulo [tex]P_i [/tex]
que tu peux constater en cliquant sur les cellules...
b)
et la ligne 259 c'est lorsque la [tex]\sqrt30k\geqslant37[/tex] les 8 [tex]P_i >31[/tex] suivant, appartenant à[37 ; 61]...ou j'ai déjà la formule des restes incrémenté;  donc en changeant la valeur de la cellule A246, les valeurs des restes de ces 8 premiers sur cette ligne, change aussi...
la ligne 270 c'est simple c'est cellule A246 - P' non marqués, de la ligne 266
ligne que l'on stock dans le tableau à côté, comme ça on les a par famille. Et si il n'y avait que des 1 pour connaître la valeur 1, et bien:
[tex]L*30k + P_i[/tex] avec [tex]P_i;[7;31][/tex] L étant le N° de la ligne....

voila le lien:
   
http://cjoint.com/?3Ahl1gIwFfE
http://cjoint.com/?3Ahl1gIwFfE

effectivement yoshi il ne s'agissait pas de [tex]\pi[/tex] mais des premiers [tex]P_i[/tex]

En fonction de vos réponses donc; pour cribler les premiers jusqu'à 10²⁸ cela risque de prendre du temps...
mon crible comporte un avantage, on peut à partir de la racine carrée de 10²⁸, stocker uniquement les premiers représentés par 1
par ligne, une ligne comporte au maximum 8 termes P.

par contre le programme avance par pas de 30....

et le nombre de divisions pour calculer le reste de 30k par P_i va nécessairement prendre du temps...à chaque pas , sauf si il reste en mémoire la formule pour chaque itération de 3(k+1), puisque les modulos P_i restent les mêmes, en gros par rapport à 30(k-1) le nombre de P_i augmente en fonction de la racine carrée de 30k.

le crible est en lui même très simple à programmer pour un informaticien bien sur..

dommage que je ne puisse  joindre le fichier excel..pour vous en faire une idée.

il me semble que
A = (1000 -190) / 2
et donc que B = A + 190