Forum de mathématiques - Bibm@th.net

Salut,

Pour apprendre le C++, je ne connais pas de bouquins...
Mais ici http://cpp.developpez.com/
tu trouveras plein de tutos, et de références de bouquins...

Je pense que déjà par exemple en Python, travailler avec un système d'exploitation 32 bits ou 64 bits change la donne : la taille des tableaux en mémoire n'est pas la même.
Python est plus agréable à apprendre même s'il est plus lent, il existe des variantes du Python "classique" qui disposent d'un compilateur et fonctions supplémentaires, tel pypy et donc plus rapides.

Si je ne me trompe pas, un programmeur qui maîtrise Python doit être capable d'adresser en parallèle les différents coeurs d'un processeur et donc répartir le travail pour gagner du temps : c'est toute la différence entre des pros et des amateurs comme moi...

@+

salut miq, tu bosses tard....

oui , c'est bien pour ça que je ne voyais pas l'intérêt de répéter cette roue qui va saturer et sans intérêt des l'instant ou tu recalcules les multiples dans l'intervalle fixé [p₁*p₂*p₃...*p_n]

je pense que tu peux programmer à partir du tableau fixé, et les tables de 8 cran T₇,T₁₁,....et T₃₁ avec comme indexe la table TD lorsque ton programme passe à un entier de la ligne suivante.
Car la taille de l'intervalle criblé, devient automatique sans que le programme s'en occupe; puisqu'il n'a qu'à calculer les 8 nouveaux cran d'une table Tp_n+1.
et le programme comme dans Eratosthène il barre les multiple tous les n crans de la table de crible , qui agit comme une grille...et c'est itératif.

donc 8 multiples par intervalle de P*8, et par table...
Sachant que ton programme part du nouveaux premier P_n, matérialisé par 1 , Ligne n, colonne P_i : {7;11;13;17;19;23;29:31}

La dernière table bien entendu, et celle du dernier [tex]1 = P_n < \sqrt X[/tex] ou X représente le nombre d'entiers à criblé, représenté par des 1,
qui change de polarité , ou se transforme en 0, en fonction du choix de programme, lorsque ce 1 est marqué par un terme ou cran, de la table T_n

est ce que tu en comprends le fonctionnement ...?

bon, ma roue ne marche pas, elle élimine au delà de ce qu'elle devrait.

il faut progresser par roues qui ne filtrent que leurs bases et pas les autres premiers de la liste, et filtrer les autres à côté. Pour ça il faut lister séparément les premiers et les crans de la roue. du coup, ça perds fortement en rentabilité...
À voir si je continue....

je pense que cette roue a une erreur le 4 au lieu du 6 qui est la différence entre 47 et 53.
[2, 3, 5, 7, 11], 13,₄. 17,₂. 19, ₄.23,₆. 29,₂ 31,₆ 37,₄ 41,₂ 43,₄ 47,₆ 53,₆ 59...etc  et à la fin ton 10, n'a rien à faire non...?
car la taille doit être 2*3*5*7, et tu part de 11 , tu n'as pas à rajouter 11,...non?
donc pour moi ta roue par de 13 et non de 11

ensuite 210*11, et tu pars de 13; intervalle des multiples à pré calculer serait [11*11,11*13....

mais tu as aussi des multiples de 7 donc pour les éliminer, tu as recalculé une roue cranté, .....?

est ce que tu peux détailler exactement, ce que tu fais pour la prochaine roue....

[2*3*5*7*11].13... ta roue devrai partir de 17....puisque l'autre est partie de 13 et non de 11;  c'est le départ qui me pose un hic....?

probablement que tes roues comportent des erreur et donc te prenne des multiples; car si tu ré incrémente cette roue, étant donné qu'elle comporte une erreur, tu la répètes pour la taille suivante

Mais je ne comprend pas pourquoi répéter ce processus avec des cran qui sont l'écart entre les premiers...d'autant que tu calcul les produits dans l'intervalle 210*11
puis 210*11*13....tu vas calculer les multiples ...pour chaque intervalle...?

oui je peut te dire quels sont les crans. je les calcule en appliquant avec la roue précédente et jusqu'à la taille prévue pour la roue courante, c'est le principe que j'essaie de mettre en place. Ceux de la roue de taille 210 sont : [4,2,4,6,2,6,4,2,4,4,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,10,2,10,2,6,6,4,6,6,2,10,2,4,2,12,10] et elle commence en 11.

Mais  on commence à avoir des non premiers genre 13*19 qui sont des calculs à ajouter en parallèle à l'application de la roue nécessaires à l'établissement de la roue suivante. Je pense que si je résous le problème que j'ai en faisant glisser les produits des ces autres premiers qui s'incrustent j'ai la méthode pour calculer toutes les roues de tailles successives.

Reste à connaître la complexité-temps de ce calcul et s'il fini par devenir plus rentable que les méthodes habituelles. À priori je pense que c'est le cas, mais ça demande finalisation et tests.

tu peux me dire quel sont les crans....?je ne pense pas, et pour moi c'est impossible; sauf peut être si tu utilises les crans dont je t'ai parlé ci dessus: roue à 8 cran avec; 7;  {12,7,4,7,4,7,12,3,} tu élimines les multiples de 7 en partant de 7,
puis en partant de 11 : {18,12,6,11,6,12,18,5} tu élimine les multiples de 11 en partant de 11 ;
...etc , mais ce serra obligatoirement 8 crans , en plus il est simple de vérifier qu'il s'agit d'une boucle itérative , comme la boucle :
6.4.2.4.2.4.6.2, qui élimine les multiple de 2, 3 et 5...

et TU NE PEUX pas changer cette boucle sans sauter des multiples

mais tu peux t'apercevoir que la taille de l'ensemble des entiers parcourus par ces boucles augmente.
7*8 =56 ;tu parcours 56 entiers et tu marques 8 multiples de 7 par itération...
11*8 =88 ; tu parcours 88 entiers et tu marques 8 multiples de 11 par itération...
13*8 = 104 ; tu parcours 104 entiers et tu marques 8 multiples de 13...

P_n * 8 = X ; tu parcours X entiers et tu marques 8 multiples de P_n par itération

tu n'as donc nul besoins de faire des multiplication uniquement de compter en partant de Pn et par rapport aux 8 termes de ta "table de 8 crans ou de 8 sauts..." que tu réitères..
ce que toi tu penses, serait d'avoir une taille de plusieurs crans , en rapport avec la table = intervalle que tu cribles; et bien non.

c'est très simple
fait un petit tableau d'entiers 30k +1 et 30k+p :

et crible comme Eratosthène en partant de 7, avec la roue de 8 cran :{12,7,4,7,4,7,12,3,}

taille de l'intervalle 7*11*13 = 1001

  7.  11.  13.   17.   .19.  23.  29.  31.
37.  41.  43.   47.   .49.  53.  59.  61.
67.  71.  73.   77.   .79.  83.  89.  91.
97. 101. 103. 107.109.113.119.121.
.........................................................
etc jusqu'à 1001
tu verras bien que ta roue de 8 crans se répète comme une boucle ou cycle tous les 7*8 entiers, si tu préfères toute les 7 lignes, et crible bien
tous les multiples de 7, change un cran ou modifie ces 8 crans et c'est le fiasco...garantie...!

tu va boucler à: 7+210 = 217
puis à 427; puis à 637, c'est à dire 7*30 + 7.

pour 11 idem tu boucles tous les 330, [11*30 + 11 = 341] avec la table {18,12,6,11,6,12,18,5} , jusqu'à 1001,
puis avec 13...etc; et quand tu arrives à la deuxième ligne, en partant de 37, tu indexes avec la roue TD {48.32.16.32.16.32.48.16} que tu rajoute à la table de 7, car c'est la même famille 30k+7
idem pour la table 41, tu part de 41 car il est premier, il n'a pas été marqué, donc tu rajoutes la table TD à la table de 11; car même famille 30k+11....etc
si tu veux les tables pour 13,1;19,23,29 et 31 soit tu les calculs ou je  les mets sur le forum...de cette discussion..tu auras les 8 tables et la table d'indexation TD.

Mais est ce que tu comprends la différence avec ta façon de cribler...
dans cette méthode pas de multiplications quelque soit la tailles des entiers de cet ensemble 30k+1, 30k+p....

Don le produit de 20 nombres premiers ne modifiera en aucun cas la taille du nombre de cran : 8 termes point barre,
par contre la taille de la roue se calcule P_n*8
par exemple pour 7 en partant de 7 et bien ta taille est 56 entiers parcourus  toutes les 7 lignes par itération
et la taille de ton crible et bien c'est toi qui le fixe .

100 000 000 000.
donc il te faut un tableau de (100 000 000 000 /3,75 = 26 666 666 666 entiers congrus à 1 ou P modulo 30 ; P :[7;29]
que tu dois établir...avant de cribler
c'est pour cela que je les remples par des 1, ou des bits ...des point....des x...ce qui prend le moins de mémoire...
sauf comme je l'ai dit, la première ligne des 8 premiers , et Ligne numéroté: N° 0.

car supposons que tu attaque la ligne 100, il faut bien que ton programme connaisse la valeur du 1 = prime et qui puisse indexer l'une des 8 première Table : T₇ à T₃₁ . avec TD

ce qui donnera  TD * 100 + T_p avec p de 7 à 31...est ce clair....?
car à chaque fois que tu marques un 1 il se transforme en 0  donc = produit...!

re
donc 7,11, ou 13.

pourquoi rajouter 11 , dans ce cas il fallait t'en tenir à 210.
puis à
2*3*5*7*11
etc..
de plus tes crans 6.4.2.4.2.4.6.2 servent uniquement à éliminer les multiple de 2,3 et 5 si tu pars au départ de 1....! et tu reboucle sur 31,37,41.....etc