Algorithme pour trouver les nombres premiers

[ansset]

De plus j'adhère à la réponse qu'a faite pm42.
donc je voyais rien à y ajouter.
-----

[iharmed]

Bonsoir
Je reviens à l’algorithme :
On dit à la machine :
Tu es l’ordinateur A1, tu vas construire l’ensemble des impaire de N, c’est simple c’est 1 + 2 puis +2 puis +2
Tu renvoi la liste, au plus grand nombre que tu as, à l’ordinateur A2 chaque fois que tu vois que ta mémoire interne risque de se saturer et tu efface les données envoyées à A2.
A toi A2 (Ai+1), tu envoi le premier nombre que tu as reçu de Ai, à l’ordinateur AP (A premier),
Tu calcule le carré de ce nombre et tu envoi aussi tous les nombres inférieurs à ce carré à AP,
Maintenant tu supprime de la liste tous les multiple du premier nombre que tu as envoyé à AP et tu procède comme suit :
Les nombres que tu vas supprimer sont répartis uniformément, tu visualise les premiers multiples et tu trouveras la répartition. Tu procède à l’effacement des multiples sans calcul tu te base uniquement sur la répartition.
Dès que tu vois que ta mémoire interne risque de se saturer tu envoi les nombres qui tu as à l’ordinateur suivant (A(i+1) et tu lui demande de faire comme toi.

Les opérations peuvent tournées à l’infini

Ça n’a rien à voir avec l’algorithme d’Ératosthène

[pm42]

Les opérations peuvent tournées à l’infini

Non.

Ça n’a rien à voir avec l’algorithme d’Ératosthène

Si à part que ça ne marche pas.

Entre ton A premier alors que A n'est pas un nombre mais le nom de l'ordinateur et le " tu envoi aussi tous les nombres inférieurs à ce carré à AP" alors qu'on avait déjà saturé la mémoire et que là, tu viens de faire un carré de ce qui est nécessaire, je corrige :

ce n'est pas un algorithme. C'est une suite de mots sans signification et le peu qui est compréhensible est massivement faux.

[iharmed]

Non.


Si à part que ça ne marche pas.

Entre ton A premier alors que A n'est pas un nombre mais le nom de l'ordinateur et le " tu envoi aussi tous les nombres inférieurs à ce carré à AP" alors qu'on avait déjà saturé la mémoire et que là, tu viens de faire un carré de ce qui est nécessaire, je corrige :

ce n'est pas un algorithme. C'est une suite de mots sans signification et le peu qui est compréhensible est massivement faux.

Bonjour

Je me suis mal exprimé.

Peut-être que je ne serais jamais me bien exprimé.

Je tente une dernière fois.

La démarche est de supprimer progressivement les non premiers et ne garder que le reste, qui est en final l’ensemble des nombres premier.
Il y 3 astuces dans ce que je propose.

La première : on établit l’algorithme pour qu’il soit traité par plusieurs machines et non une seule, car on n’arrête les calculs que lorsque les machines atteignent leurs limites.

La deuxième : c’est vider la mémoire de la machine en supprimant les données utilisées et en transmettant les données utiles à une autre machine (ou à un autre processus de la même machine). Ainsi elle pourra continuer sur sa tâche.

La troisième, la plus importante : est comment supprimer les non premiers ? Lorsque on supprime les multiples de 2, il reste les nombres impairs. On va ensuite supprimer les multiples de 3 ; l’astuce est que dans l’ensemble des impaire les multiples de 3 sont répartis uniformément (1 sur 3) et la machine n’a pas besoin de calculer, elle supprimer un nombre, saute 2 nombres et supprime le troisième.
Dans l’ensemble obtenu qui est sans les multiples de 2 et sans les multiples des 3, il faudra supprimer les multiple de 5. Là aussi ils sont répartis uniformément, il suffit que la machine connaisse la répartition. Elle peut trouver elle-même cette répartition par des teste à faire avant d’entamer sa tâche.

Et voila

Je le fais sur EXCEL, et ça marche

[ansset]

ça reste le principe d’Ératosthène.
rajouter plusieurs ordinateurs ( en vidant, reversant, etc ... ) ne fait que compliquer la démarche.

[iharmed]

ça reste le principe d’Ératosthène.
rajouter plusieurs ordinateurs ( en vidant, reversant, etc ... ) ne fait que compliquer la démarche.

Ce que a dit Ératosthène se base sur un principe narurel.
Les nombres premiers c'est ce qui reste si on supprime les non premiers. Si Ératosthène ne la pas dit ce principe sera la

[ansset]

Il n'a pas besoin de le dire pour le faire !!!!

L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers.

On commence par rayer les multiples de 2, puis à chaque fois on raye les multiples du plus petit entier restant.

On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment.
À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N.

[pm42]

C'est sans espoir. Depuis le début, c'est le crible et il ne veut pas le reconnaitre.
Et c'est la même chose sur son algorithme : c'est du nawak mais à toute objection, la réponse est "mais si ça marche"...

[CM63]

Bonjour

Je me suis mal exprimé.

Peut-être que je ne serais jamais me bien exprimé.

En effet, l'hypothèse n'est pas à rejeter.

Je tente une dernière fois.

La démarche est de supprimer progressivement les non premiers et ne garder que le reste, qui est en final l’ensemble des nombres premier.

C'est exactement ce que fait Ératosthène.

Il y 3 astuces dans ce que je propose.

La première : on établit l’algorithme pour qu’il soit traité par plusieurs machines et non une seule, car on n’arrête les calculs que lorsque les machines atteignent leurs limites.

La deuxième : c’est vider la mémoire de la machine en supprimant les données utilisées et en transmettant les données utiles à une autre machine (ou à un autre processus de la même machine). Ainsi elle pourra continuer sur sa tâche.

Ça c'est de l'ordre de la mise en œuvre de l'algorithme, pas de sa définition.

La troisième, la plus importante : est comment supprimer les non premiers ? Lorsque on supprime les multiples de 2, il reste les nombres impairs. On va ensuite supprimer les multiples de 3 ; l’astuce est que dans l’ensemble des impaire les multiples de 3 sont répartis uniformément (1 sur 3) et la machine n’a pas besoin de calculer, elle supprimer un nombre, saute 2 nombres et supprime le troisième.
Dans l’ensemble obtenu qui est sans les multiples de 2 et sans les multiples des 3, il faudra supprimer les multiple de 5. Là aussi ils sont répartis uniformément, il suffit que la machine connaisse la répartition. Elle peut trouver elle-même cette répartition par des teste à faire avant d’entamer sa tâche.

Ca , ce n'est pas une astuce, c'est l'algorithme lui-même.

Je le fais sur EXCEL, et ça marche.

Ça , c'est de l'ordre de la mise en œuvre.

[Deedee81]

Salut,

A noter que les astuces pour améliorer/optimiser l'algorithme d’Ératosthène, il y en a d'autres et plus efficace. J'ai déjà fait (qui ne l'a pas fait d'ailleurs ).
Et dans le cas de plusieurs machines, il est évident que ça peut accélérer, mais ça nécessite des méthodes plus complexes pas du tout décrite par iharmed.
(ou même pour du multi-processeur. Là non plus ce n'est pas trivial, et là aussi j'ai donné même si c'était sur du plus complexe : de la synchro d'exécution de taches complexes client - serveur).
Mais peu importe, tout ça c'est une question d'implémentation informatique, ça n'a rien à voir en soi avec le choix de l'algorithme comme le dit bien Cm63

[iharmed]

Bonjour

..

La troisième, la plus importante : est comment supprimer les non premiers ? Lorsque on supprime les multiples de 2, il reste les nombres impairs. On va ensuite supprimer les multiples de 3 ; l’astuce est que dans l’ensemble des impaire les multiples de 3 sont répartis uniformément (1 sur 3) et la machine n’a pas besoin de calculer, elle supprimer un nombre, saute 2 nombres et supprime le troisième.
Dans l’ensemble obtenu qui est sans les multiples de 2 et sans les multiples des 3, il faudra supprimer les multiple de 5. Là aussi ils sont répartis uniformément, il suffit que la machine connaisse la répartition. Elle peut trouver elle-même cette répartition par des teste à faire avant d’entamer sa tâche.

bonjour
"Là aussi ils sont répartis uniformément", je le dis car j'espère que sa soit vrai.

malheureusement c'est faux.

à partir du nombre 19 ce n'est plus uniformément répartit !!!!

[CM63]

Tu parlais des multiples de 5: bien sur que si, ils sont répartis uniformément.

[iharmed]

Tu parlais des multiples de 5: bien sur que si, ils sont répartis uniformément.

Oui
Mais pas ceux de 19

[ansset]

ben si, comme les autres N
+N à chaque fois..

[Deedee81]

Salut,

Ben, oui, je confirme. Les multiples de 19 :
19 - 38 - 57 - 76 - etc...
Et séparation entre chaque nombre :
19 - 19 - 19 - etc....
C'est uniformément répartit.

..... forcément !

[pm42]

S
C'est uniformément répartit.

Je pense qu'il pensait que c'était uniformément réparti dans l'espace où on a déjà viré les diviseurs précédents. C'est en tout cas ce que j'avais supposé quand il décrivait son "algorithme multi-machine".
C'est faux à partir de 3 bien sur et 19 n'a rien de particulier.

Un nawak de plus sur ce fil, ce n'est pas la premier ni le pire

[Deedee81]

Je pense qu'il pensait que c'était uniformément réparti dans l'espace où on a déjà viré les diviseurs précédents. C'est en tout cas ce que j'avais supposé quand il décrivait son "algorithme multi-machine".
C'est faux à partir de 3 bien sur et 19 n'a rien de particulier.

En effet. Il faudrait que iharmed précise, mais bon, je vois mal comment ça pourrait être correct.

Un nawak de plus sur ce fil, ce n'est pas la premier ni le pire

Un petit HS pour bien préciser la situation :

Je dirais même, un de plus (de nawak) sur le forum. Malgré qu'on est un forum modéré, c'est parfois désolant (enfin, j'ai vu pire, le pire de tous étant sans doute le forum de physique de usenet, en anglais. Archi bourré de pub, de messages hors sujets, d'insultes .... a tel point que même les messages nawak ne représentent qu'une petite fraction.... elle même bien plus importante que les messages corrects. Et le mieux que j'ai vu est le forum de recherche en physique usenet en anglais, tous les messages devant d'abord passer par le modérateur..... avec un forum super impeccable et même avec un contenu formidable mais....... un débit de message désespéramment lent. Je pense que Futura représente le meilleur juste milieu malgré ces "petits plaisanteries", pour le dire comme ça, qu'on voit passer. Certaines étant dues simplement à une question de niveau, je pense que c'est le cas ici, et après tout, tout le monde est le bienvenu ).

Mais même en science ludique ça va finir par tourner au vert
J'éviterai toutefois d'être juge et partie comme d'hab (un fil récent a par exemple été judicieusement nettoyé et fermé par Albanxiii sans même que je le demande, ce que j'aurais dû faire mais j'ai hésité car j'avais moi-même répondu à la question initiale).

[pm42]

Je pense que Futura représente le meilleur juste milieu malgré ces "petits plaisanteries", pour le dire comme ça, qu'on voit passer.

Vu que le but est la vulgarisation, il faut en effet laisser une certaine latitude. Sinon et comme tu le fais remarquer, on se retrouve avec un forum "de référence", très bon niveau mais où les spécialistes parlent aux spécialistes.

La frustation vient sans doute de cas comme celui-ci où il n'y pas vraiment de dialogue. Ceci dit, iHarmed est gentil, poli et il ne prend pas les autres de haut ni pour des cons.
C'est déjà beaucoup.

[CM63]

Oui
Mais pas ceux de 19

Ben si, pareil, il ont une période de 19

[Deedee81]

Ben si, pareil, il ont une période de 19

On l'avait déjà dit deux fois. je sais bien qu'il faut enfoncer les clous, mais là

[pm42]

On l'avait déjà dit deux fois. je sais bien qu'il faut enfoncer les clous, mais là

Je ne sais plus qui faisait remarquer ça, peut-être albanxiii, que la plupart des gens répondent sans lire ce qu'on écrit les autres.

[Deedee81]

Je ne sais plus qui faisait remarquer ça, peut-être albanxiii, que la plupart des gens répondent sans lire ce qu'on écrit les autres.

On peut pas en parler ici, ce n'est pas une discussion sur les statistiques

[CM63]

Je ne sais plus qui faisait remarquer ça, peut-être albanxiii, que la plupart des gens répondent sans lire ce qu'on écrit les autres.

Tout-à-fait, ou plutôt je réponds aux messages juste après les avoir lus, et avant de lire les réponses des autres. Ma pile de parenthèses a des limites

[Deedee81]

Ma pile de parenthèses a des limites

Passe en mode Forth

[albanxiii]

Tout-à-fait, ou plutôt je réponds aux messages juste après les avoir lus, et avant de lire les réponses des autres. Ma pile de parenthèses a des limites

Sauf cas où j'ai besoin de me soulager, j'essaye de ne répondre que si j'apporte quelque chose de nouveau à la discussion.
Mais chacun est libre de faire comme bon lui semble, seule la charte impose des limites, et c'est très bien ainsi.

[Deedee81]

En tout cas, on comment tous ce genre d'erreur. Parfois même il m'est arrivé de parcourir la discussion et de bypasser un passage important sans m'en rendre compte. On n'est pas des machines.

Mais répondre avant de lire les réponses des autres est clairement une erreur.

[iharmed]

ben si, comme les autres N
+N à chaque fois..

on cherche la répétition des multiples de 19 dans l’ensemble duquel on a supprimé les multiple de 2, 3, 5, 7, 11 et 13.
essaye de trouver la répartition

[iharmed]

on cherche la répétition des multiples de 19 dans l’ensemble duquel on a supprimé les multiples de 2, 3, 5, 7, 11 et 13.
essaye de trouver la répartition

bonjour
on supprimant les multiples de 2, 3, 5, 7, 11, 13 et 17 (via ECXEL) je trouve les nombres premiers suivants :
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,

l'ensemble des entiers qui me reste et duquel je doit supprimer les multiples de 19 est le suivant :
361, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 437, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 529, 541, 547, 551, 557, 563, 569, 571, 577, 587, 589, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 691, 701, 703, 709, 713, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 779, 787, 797, 809, 811, 817, 821, 823, 827, 829, 839, 841, 851, 853, 857, 859, 863, 877, 881, 883, 887, 889, 893, 899,

dites moi comment sont répartis les multiples de 19 pour pouvoir les supprimer sans faire trop de calcul ?

[iharmed]

bonjour
voila les multiples de 19 en rouge, leurs répartition n'est pas uniforme (je pense)

361, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 437, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 529, 541, 547, 551, 557, 563, 569, 571, 577, 587, 589, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 667, 673, 677, 683, 691, 701, 703, 709, 713, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 779, 787, 797, 809, 811, 817, 821, 823, 827, 829, 839, 841, 851, 853, 857, 859, 863, 877, 881, 883, 887, 889, 893, 899,

[pm42]

Oui et les multiples de 11, 13 et 17 sont uniformes ?