Répondre à la discussion
Page 1 sur 5 12 3 4 DernièreDernière
Affichage des résultats 1 à 30 sur 127

Algorithme pour trouver les nombres premiers




  1. #1
    iharmed

    Algorithme pour trouver les nombres premiers

    Bonjour

    Je commence par une description naïve avant de développer l’algorithme analytiquement.

    On pose tous les nombres premiers dans de petites boite sur une ligne allant vers l’infinie. On ne prend pas le 1 et le 2 car ils sont premiers par définition.
    La boite 1 contient le 3, la boite 2 le 4, la boite 3 le 5 et ainsi de suite ….

    On commence l’algorithme

    Une première personne commence.
    Elle prend la première boite et la remet avec le nombre qu’elle contienne (c‘est le 3) à monsieur RNP « ramasseur des nombres premiers ».
    Elle ouvre les boites restantes, une boite sur 2,
    la première boite qui est devant elle (contient le nombre 4) la jette dans la poubelle
    la 2eme boite (contient le nombre 5) elle la saute
    la 3eme boite (contient le nombre 6), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
    la 4eme boite (contient le nombre 7) elle la saute (il procède une sur deux)
    la 5eme boite (contient le nombre 8), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
    …. Et elle continue ainsi sans s’arrêter
    Ainsi on aura au sol, les boites contenant les nombres : 5, vide, 7, vide, 9, vide, 11, vide, 13, vide, 15, ……,

    Une deuxième personne prend le relai et fait exactement la même chose mais cette fois elle ouvre les boites une sur 3 (elle a un pas plus allongé que la personne précédente).
    Elle prend la première boite et la remet avec le nombre qu’elle contienne (c‘est le 5) à monsieur RNP « ramasseur des nombres premiers ».
    Elle ouvre les boites restantes, une boite sur 3,
    la première boite qui est devant elle (elle est vide) la jette dans la poubelle
    la 2eme boite (contient le nombre 7) et la 3eme boite (vide), elle les sautes
    la 4eme boite (contient le nombre 9), elle l’ouvre prend le nombre qu’elle contient et remet le boite vide à sa place
    …. Et elle continue ainsi sans s’arrêter
    Ainsi on aura au sol, les boites contenant les nombres : 7, vide, vide, vide, 11, vide, 13, vide, vide, vide, 17,

    La 3eme personne à un pas plus allongé et elle ouvre les boites une sur 4,
    Si vous vérifiez vous allez trouver que :
    Elle remet la boite contenant le 7 à monsieur RNP
    Elle ne trouvera que les boites vides

    Ceci est un algorithme, mais comment le transformer en analytique

    -----

    Dernière modification par iharmed ; 15/03/2019 à 23h25.

  2. Publicité
  3. #2
    choom

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par iharmed Voir le message
    Bonjour

    ...
    Ceci est un algorithme, mais comment le transformer en analytique
    Bonsoir.

    Que veux-tu dire exactement par «*transformer en analytique*» ?

    Est-ce décrire formellement en langage mathématique ces opérations effectuées sur les nombres entiers, ainsi que le résultat obtenu ( à condition de s’imposer une limite à sa promenade, car l’infini c’est loin ...) ?

    Nb: c’est une version perso d’un crible connu depuis l’antiquité.

    Bien cordialement,
    Choom

  4. #3
    pm42

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par choom Voir le message
    Nb: c’est une version perso d’un crible connu depuis l’antiquité.
    En effet : https://fr.wikipedia.org/wiki/Crible_d%27Ératosthène. Et ce n'est pas pratique pour trouver des grands nombres premiers qui est ce qu'on cherche.


  5. #4
    iharmed

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par pm42 Voir le message
    En effet : https://fr.wikipedia.org/wiki/Crible_d%27Ératosthène. Et ce n'est pas pratique pour trouver des grands nombres premiers qui est ce qu'on cherche.
    BONJOUR
    En réalité je ne sais pas ce que je veux,
    Je m’amuse c’est tout

    J’utilise l’EXCEL pour trouver les nombre premier en procédant par criblage, ceci ne pourra s’appeler qu’algorithme.
    J’écris tous les nombres du 2 à N.
    Je mets dans le panier des nombres premiers le premier nombre de la liste (c’est le 2)
    Je supprime tous les nombres multiples de 2 mais sans utiliser les calculs en les supprimant un nombre sur 2
    Il me reste unique les nombres impairs, et je mets dans le panier le nombre 3
    Je vais procéder ensuit à l’élimination des multiple de 3 et je remarque que le premier multiple de 3 qui reste dans la liste est le carré du 3 et je prends tous les nombres inférieur à ce carré (le 5 et le 7 ) et je les met dans le panier. Nom panier des nombres premier contient (2, 3, 5 et 7)
    Pour supprimer les multiple de 3, sans utiliser les calcule, je constate qu’ils sont répartis 1 sur 3, ils sont facilement repérables : 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55,
    Il reste dans la liste les nombres suivants : 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 71, 73, 77, 79, 83, 85
    je mets dans le panier le nombre 11 (premier nombre de la liste)
    Je procède ensuit à l’élimination des multiple de 5 (c’est le nombre premier qui suit le 3 dans le panier)
    Le premier multiple est le 25, le carré de 5 et comme précédemment pour le 3 je prends tous les nombres inferieur à ce carré et je les mets dans le panier (2, 3, 5, 7, 11, 13, 17, 19 et 23), mon panier grandit rapidement
    Pour supprimer les multiple de 5 sans utiliser les calcule je constate qu’ils sont répartis uniformément ; je supprime le premier, je saute 2 nombres et je supprime le suivant puis je saute 6 et je reviens à sauter puis 6 puis 2 puis 6 (je note pour le nombre 5 la répartition (2 , 6))
    25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 71, 73, 77, 79, 83, 85

    Maintenant pour le 7
    En résumé les nombres inférieurs au carré de 7 (49) sont à mettre dans le panier (29, 31, 37, 41, 43, 47)
    Pour supprimer les multiples de 7 la répartition est (6 , 3)
    Pour les multiples de de 11 la répartition est (3 , 5)
    Pour les multiples de de 13 la répartition est (8 , 6)

    En connaissant la répartition des nombres premiers, la création d’un programme deviendra facile

    En arrivant à 13 soit 5 opération j’ai dans le panier 60 nombre premier

  6. #5
    ansset

    Re : Algorithme pour trouver les nombres premiers

    reste que tu ré écris ( en plus compliqué ) ce qui a été déjà proposé dès l'antiquité.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. A voir en vidéo sur Futura
  8. #6
    iharmed

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par ansset Voir le message
    reste que tu ré écris ( en plus compliqué ) ce qui a été déjà proposé dès l'antiquité.
    Bonsoir
    Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité. Ce n’était pas dans les cours.

    Je cherche une méthode (la plus simple) avec les moyens d'aujourd’hui

  9. #7
    ansset

    Re : Algorithme pour trouver les nombres premiers

    ici :
    https://fr.wikipedia.org/wiki/Crible...atosth%C3%A8ne
    ( III siècle A JC)
    et une version améliorée bien plus récente ( et plus complexe )
    https://fr.wikipedia.org/wiki/Crible_d%27Atkin
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  10. Publicité
  11. #8
    pm42

    Re : Algorithme pour trouver les nombres premiers

    Le lien a été donné dès le 3ème message.
    Bon courage parce que je ne sens pas ici une volonté d'apprendre, juste de réinventer la roue en la faisant carrée.

  12. #9
    albanxiii

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par iharmed Voir le message
    Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité. Ce n’était pas dans les cours.
    Ceci n'est pas une justification acceptable, sauf à votre paresse intellectuelle.
    Heureusement que tout le monde ne raisonne pas de cette façon, sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos.

    (la prochaine fois que mon chef trouvera que mon travail n'avance pas assez vite, je lui sortirai cet argument, on verra bien )
    Dernière modification par albanxiii ; 17/03/2019 à 06h14.
    Not only is it not right, it's not even wrong!

  13. #10
    ansset

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par pm42 Voir le message
    Le lien a été donné dès le 3ème message.
    oui, exact ! désolé pour la redite sans citation.....
    j'en rajoute un autre bien plus complexe, pour exciter les neurones, mais il n'a certainement pas été vu en cours.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  14. #11
    LeMulet

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par albanxiii Voir le message
    Heureusement que tout le monde ne raisonne pas de cette façon, sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos.
    Heureusement que certains raisonnent de cette façon (essayer par soi-même avant de copier sur le voisin), sinon on serait encore dans des grottes avec des peaux de bêtes sur le dos...
    Bonjour, et Merci.

  15. #12
    Deedee81

    Re : Algorithme pour trouver les nombres premiers

    Salut,

    Bon, c'est quand même mieux que d'être dans des peaux de bêtes avec des grottes sur le dos
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  16. #13
    Olivzzz

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par Deedee81 Voir le message
    Salut,

    Bon, c'est quand même mieux que d'être dans des peaux de bêtes avec des grottes sur le dos
    C'est pas très gentil de se moquer ainsi des tortues !

  17. #14
    vgondr98

    Re : Algorithme pour trouver les nombres premiers

    Bonjour, comme je me s'y mis à la programmation avec R, je viens d'écrire un programme permettant d'afficher la liste des nombres premiers jusqu'à N.
     Cliquez pour afficher
    Dernière modification par JPL ; 17/03/2019 à 22h05. Motif: Ajout de la balise Code (#) pour garder l'indentation

  18. #15
    iharmed

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par vgondr98 Voir le message
    Bonjour, comme je me s'y mis à la programmation avec R, je viens d'écrire un programme permettant d'afficher la liste des nombres premiers jusqu'à N.
     Cliquez pour afficher
    Bonsoir
    Écrire sous forme informatique un algorithme c'est banale.
    Il faut d'abord trouver l'algorithme.
    Tu procédera comment pour trouver les nombres premiers
    Si tu dis que je prend un nombre et je le divise pour voir s'il est premier alors c'est pas la peine de continuer
    Dernière modification par iharmed ; 17/03/2019 à 22h23.

  19. #16
    pm42

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par iharmed Voir le message
    Bonsoir
    Écrire sous forme informatique un algorithme c'est banale.
    Il faut d'abord trouver l'algorithme.
    Tu procédera comment pour trouver les nombres premiers
    Si tu dis que je prend un nombre et je le divise pour voir s'il est premier alors c'est n'est pas peine de continuer
    Il a justement implémenté un crible.
    Je ne sais pas trop quoi dire : entre le très, très faible niveau de ce que tu as présenté (et je suis gentil), ton refus d'apprendre et maintenant, le besoin de déprécier ce qu'à fait quelqu'un d'autre, il est difficile de te parler en restant des les limites de la charte et de la politesse.

  20. #17
    iharmed

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par iharmed Voir le message
    Bonsoir
    Je ne sais pas ce qui a était dit au sujet de la recherche des nombres premiers à l'antiquité
    Correction
    Je ne sais pas ce qui a été dit au sujet de comment trouver tous les nombres premiers,
    À ce jour on sait pas le faire

  21. #18
    ansset

    Re : Algorithme pour trouver les nombres premiers

    ce n'est certainement pas avec ton approche qu'on en prend le chemin.
    car comme toutes les autres ( plus ou moins sophistiquées ) , elle conduit à les lister au fur et à mesure.
    et encore une fois , c'est une sous version de l'approche la plus ancienne.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  22. #19
    LeMulet

    Re : Algorithme pour trouver les nombres premiers

    Vous me donnez n'importe quel nombre, je vous dis s'il est premier.
    (C'est une astuce mais bon je ne suis pas mathématicien...)
    Bonjour, et Merci.

  23. #20
    Deedee81

    Re : Algorithme pour trouver les nombres premiers

    Salut,

    Citation Envoyé par LeMulet Voir le message
    Vous me donnez n'importe quel nombre, je vous dis s'il est premier.
    (C'est une astuce mais bon je ne suis pas mathématicien...)
    Je crois que j'ai deviné

    Concernant le sujet, une question fort intéressante n'est pas tant d'avoir un algorithme qui donne les nombres premiers, ça c'est assez facile, mais d'avoir des algorithmes efficaces pour tester si un grand nombre est premier. Il y a pas mal de littérature sur le net à ce sujet.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  24. #21
    vgondr98

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par Deedee81 Voir le message
    Il y a pas mal de littérature sur le net à ce sujet.
    http://villemin.gerard.free.fr/Wwwgv...r/testprim.htm

  25. #22
    LeMulet

    Re : Algorithme pour trouver les nombres premiers

    Non, mais c'est trop facile ça (Le boulot est déjà fait, il suffit de suivre le mode d'emploi ).
    Bonjour, et Merci.

  26. #23
    ansset

    Re : Algorithme pour trouver les nombres premiers

    c'est juste.
    mais comme ce sujet est une marotte pour beaucoup de mathématiciens depuis fort longtemps, il n'est pas étonnant qu'il ait déjà fait couler beaucoup d'encre.
    faire du nouveau sur le sujet n'est donc pas chose aisée.
    de fait, on "améliore" à chaque fois un peu plus l'optimisation......
    Citation Envoyé par iharmed Voir le message
    Je ne sais pas ce qui a été dit au sujet de comment trouver tous les nombres premiers,
    À ce jour on sait pas le faire
    non, on ne sait pas faire.
    et ce serait la médaille Fields assurée.
    alors bon courage....
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  27. #24
    LeMulet

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par ansset Voir le message
    non, on ne sait pas faire.
    et ce serait la médaille Fields assurée.
    alors bon courage....
    Moi je sais faire (en sciences ludiques bien sûr).
    Allez-y, donnez-moi n'importe quel nombre, aussi grand que vous voulez, et je vous dis s'il est premier en quelques instants.
    Bonjour, et Merci.

  28. #25
    ansset

    Re : Algorithme pour trouver les nombres premiers

    je joue le jeu.
    prenons les 500 chiffres de pi après la virgule.
    je ne vais pas les lister.

    ps : même si ce n'est pas le but de Iharmed qui les veux tous , et pas dire si l'un ou un autre l'est ou pas.
    Dernière modification par ansset ; 18/03/2019 à 12h53.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  29. #26
    iharmed

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par LeMulet Voir le message
    Moi je sais faire (en sciences ludiques bien sûr).
    Allez-y, donnez-moi n'importe quel nombre, aussi grand que vous voulez, et je vous dis s'il est premier en quelques instants.
    bonjour
    10^109 + 11^119 + 4

    sachant que 10^109 + 11^119 + 3 est paire
    Dernière modification par iharmed ; 18/03/2019 à 13h33.

  30. #27
    Deedee81

    Re : Algorithme pour trouver les nombres premiers

    Arf, bande de vicieux. Je m'attendais à tout sauf à ça. Je me demande ce que LeMulet a prévu
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  31. #28
    ansset

    Re : Algorithme pour trouver les nombres premiers

    un gros gag, certainement....
    il avait prévenu du coté "ludique".
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  32. #29
    ansset

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par iharmed Voir le message
    bonjour
    10^109 + 11^119 + 4

    sachant que 10^109 + 11^119 + 3 est paire
    divisible par 5, c'est quasi immédiat.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  33. #30
    Deedee81

    Re : Algorithme pour trouver les nombres premiers

    Citation Envoyé par ansset Voir le message
    divisible par 5, c'est quasi immédiat.
    Ah oui, tiens, bien vu ça
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

Page 1 sur 5 12 3 4 DernièreDernière

Discussions similaires

  1. Nombres premiers et algorithme ?
    Par jean reaver dans le forum Mathématiques du collège et du lycée
    Réponses: 33
    Dernier message: 13/09/2018, 18h57
  2. algorithme revolutionnaire des nombres premiers
    Par Guillaume Hawing dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 15/09/2016, 11h34
  3. Réponses: 36
    Dernier message: 20/09/2013, 15h16
  4. nombres premiers en algorithme
    Par dalida1111 dans le forum Programmation et langages, Algorithmique
    Réponses: 3
    Dernier message: 30/11/2011, 21h57
  5. Algorithme pour nombres premiers.
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 22/05/2005, 22h28