Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 34

Nombres premiers et algorithme ?



  1. #1
    jean reaver

    Nombres premiers et algorithme ?

    Voici un algorithme simple pour générer tous les nombres premers,sans recours à la crible d'Ératosthène.Je l'ai écrit en Qbasic.
    2-2^n mod n=0

    le logiciel c'est Justbasic

    rem Prim gen
    for n= 1 to 1000
    u=2-2^n mod n
    if u mod n=0 then
    print n
    end if
    next n

    https://www.justbasic.com/download.html
    Télécharger le logiciel free puis copier coller le paragraphe "rem Prim gen" .Il suffit de changer les valeurs 1000,10000,ETC... Pour obtenir la quantité recherchée.Tester et donner avis?

    -----


  2. Publicité
  3. #2
    jacknicklaus

    Re : Nombres premiers et algorithme ?

    33 et 42 sont premiers ?
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  4. #3
    gg0

    Re : Nombres premiers et algorithme ?

    Bonjour.

    Cette méthode est connue, mais échoue, par exemple avec 561=3*11*17 qui apparaît dans la liste. Voir nombre de Carmichael sur Wikipédia. elle est aussi très gourmande en place mémoire pour n grand.

    Quant au programme, recalculer u modulo n alors que u est déjà modulo n est superfétatoire.

    Cordialement.

  5. #4
    jean reaver

    Re : Nombres premiers et algorithme ?

    33 42 explique ?

  6. #5
    gg0

    Re : Nombres premiers et algorithme ?

    Pour ma part, ils ne sont pas sortis dans l'application de l'algorithme (j'ai repris quasiment le même avec Maple). 561, lui était présent.

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

    Re : Nombres premiers et algorithme ?

    les erreurs sont très minimes même si le 561 apparaît .Pour l'instant ils n'existe aucun algo au monde pour générer les premiers,hormis la crible d'Ératosthène.Je pense c'est le meilleur pour l'instant.Peut donner une explication sur la répatitions des premiers .Connu ou non connu .Si on a pas en main un algorithme ,en cherche un asturce.Il suffit de boucler un Test de primalitè tel AKS ou autre .Ici c est le bouclage du test AKS avec une simplfication .(x-1)^n-(x^n-1)=(x-1)^n-x^n+1=x-x^n.

  9. Publicité
  10. #7
    jean reaver

    Re : Nombres premiers et algorithme ?

    GGO si vraiment vs comprener cela c'est vous êtes assez fort parceque c'est très difficiles .

  11. #8
    jean reaver

    Re : Nombres premiers et algorithme ?

    si la somme des chiffres d'un nombre est égal a 6 ,le nombre est divisible par 3 .
    3+3=6
    4+2=6
    33/3=11
    42/3=14
    ne sont pas premiers

  12. #9
    jean reaver

    Re : Nombres premiers et algorithme ?

    la methode n'echoue pas il suffit de filtrer les nombres de carmichael tel 561.

  13. #10
    jean reaver

    Re : Nombres premiers et algorithme ?

    voici une methode
    Les nombres dont la somme de leurs chiffres 3 6 9 ,ils sont divisible par trois :
    12=1+2=3
    15 et 51
    24 et 42
    33

  14. #11
    gg0

    Re : Nombres premiers et algorithme ?

    Pourquoi mélanger le test de divisibilité par 3, accessible a un écolier, à la question de la génération des nombres premiers. Avec les ordinateurs actuels, on a facilement la liste des premiers inférieurs à un milliard, et le temps le plus long est celui de l'affichage. Donc le choix de la méthode est vite fait. En fait, on ne s'intéresse plus qu'à des moyens de prouver la primalité de nombres de 100 à 200 chiffres assez rapidement pour les usages techniques (cryptographie, par exemple).

    Il est facile de trouver des documents sur le sujet, y compris romancés, puis, si on veut vraiment faire œuvre utile (et pas refaire ce que des milliers de débutants ont fait), étudier sérieusement la théorie des nombres.

    Cordialement.

  15. #12
    Paraboloide_Hyperbolique

    Re : Nombres premiers et algorithme ?

    Bonjour,

    Citation Envoyé par jean reaver Voir le message
    Pour l'instant ils n'existe aucun algo au monde pour générer les premiers,hormis la crible d'Ératosthène.Je pense c'est le meilleur pour l'instant.
    Vous devriez vous documenter un tant soit peu avant de sortir de telles affirmations...

  16. Publicité
  17. #13
    eudea-panjclinne

    Re : Nombres premiers et algorithme ?

    Citation Envoyé par gg0
    puis, si on veut vraiment faire œuvre utile (et pas refaire ce que des milliers de débutants ont fait), étudier sérieusement la théorie des nombres.
    Je pense que l'on peut faire des mathématiques en amateur, ce que je fait depuis longtemps et rechercher des démonstrations déjà faites de nombreuses fois, cela me donne un certain plaisir dont je ne me lasse pas. Est-ce vraiment faire oeuvre utile ? J'avoue ne pas me poser la question, oeuvre aussi utile certainement que celui qui fait des mots croisés ou lit des roman policiers.

    @jean reaver
    on ne peut que vous féliciter de pratiquer à votre niveau, en amateur, des mathématiques et plus précisément de l'Arithmétique et, vous encourager dans cette voie. Cependant, il faut que vous compreniez que les mathématiques que vous pratiquez sont élémentaires (niveau Lycée), très loin des niveaux de recherche actuel. Ainsi, vous utilisez le Petit théorème de Fermat, connu depuis le 17e siècle, sur lequel des générations de mathématiciens ont certainement dit tout ce qu'il y avait à dire d'élémentaire à son sujet. De plus, vous utilisez la réciproque de ce théorème qui est fausse. Il serait bien, pour votre progression futur, de tenir compte des avis qui vous sont donnés et comme dit plus haut de vous documenter quelque peu sur les questions que vous cherchez. Que ceci ne vous empêche pas de continuer vos recherches, mais en gardant à l'esprit que d'autres les ont déjà résolu depuis longtemps.
    Dernière modification par eudea-panjclinne ; 04/09/2018 à 13h17.

  18. #14
    jean reaver

    Re : Nombres premiers et algorithme ?

    En mathématiques, la recherche de formules exactes donnant tous les nombres premiers (ou même donnant uniquement certains des nombres premiers) s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées.

  19. #15
    mach3

    Re : Nombres premiers et algorithme ?

    que dire alors de la formule de Minac?

    https://forums.futura-sciences.com/s...-premiers.html

    m@ch3
    Never feed the troll after midnight!

  20. #16
    jean reaver

    Re : Nombres premiers et algorithme ?

    @ eudea
    Est ce que vous avez testé l'algo sur le logiciel que j'ai mis ?Puis de raconter des choses?le reciproque du petit theorème de fermat donnent tous les nombres premiers.Mais Ils sont associé avec les nombres de carmichael tel le 561,1 729 ...etc
    Si 2^(n-1) mod n = 1 est vrai .Alors le reciproque c'est faux.Le reciproque est vrai si a-a^n mod n=0 remarque la différence ?! entre le 1 et 0.J'ai trvaillé sur pour qu'il soit vrai je suis arrivé à ces conclusions.

    rem Prim gen
    for n= 1 to 1000
    u=2-2^n
    if u mod n=0 then
    print n
    end if
    next n

    copie coller sur l'application

  21. #17
    gg0

    Re : Nombres premiers et algorithme ?

    Pourquoi republier un algorithme qui ne marche pas ? Et ça t'a été expliqué.

    Tu fais tout ce qu'il faut pour qu'on ne te prenne pas au sérieux, dommage !

  22. #18
    jean reaver

    Re : Nombres premiers et algorithme ?

    la formule qui "simule" le crible d’Ératosthène

  23. Publicité
  24. #19
    jall2

    Re : Nombres premiers et algorithme ?

    bonjour

    Il existe une variante du test de Fermat, le test de Miller Rabin, beaucoup plus efficace.
    On peut tester la primalité d'un nombre n simplement, rapidement, et de manière déterministe jusqu'à n=3317044064679887385961981 (voir la suite OEIS A014233)
    Au delà, on peut garder un test déterministe, mais cela suppose d'admettre l'hypothèse du continu généralisée et le temps de test peut être prohibitif.
    Sinon, on peut utiliser le test de manière probabiliste, tout en sachant calculer un majorant de la probabilité de se tromper
    Dernière modification par jall2 ; 06/09/2018 à 09h38.

  25. #20
    jall2

    Re : Nombres premiers et algorithme ?

    erreur, c'est pas l'hypothèse du continu, mais l'hypothèse de Riemann

  26. #21
    ansset

    Re : Nombres premiers et algorithme ?

    Citation Envoyé par jean reaver Voir le message
    les erreurs sont très minimes même si le 561 apparaît (….)
    des modèles comme ça, on en voit plein, mais une seule erreur suffit à "casser" l'algorithme de base.
    bon courage ! d'autant que plein d'autres avant toi ont bossés la dessus ! ( peut être ignores tu leurs travaux ? )
    Dernière modification par ansset ; 06/09/2018 à 11h33.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  27. #22
    jean reaver

    Re : Nombres premiers et algorithme ?

    Concernant l'algoritm de carmichael :
    p=6*n+1
    q=12*n+1
    r=18*n+1
    N=p*q*r
    si p,q et r sont premiers
    ex:1729
    (6*1+1)(12*1+1)(18*1+1)
    7*13*17
    Est qu'l les donnent tous ou bien non ?

  28. #23
    jean reaver

    Re : Nombres premiers et algorithme ?

    le petit théorème de fermat c'est : a^(n-1) mod n=1
    a etant la base
    n est le nombre que l'on doit tester
    si n est premier c'est toujours =1,dans toutes les bases.
    Si n est diffrent de 1 ,alors est premier.Mais Ils existes des nombres qui affichent
    le même résultat,par conséquent égal à 1.Ce qu'on désigne par pseudo premiers.
    J'apporte la correction :FERMAT ne précise pas ou se trouve la vérité.On se conte d'une
    seule ,puis on dit que c'est faux !il faut passer par plusieurs bases .le test est détérmiste.
    ex:la valeur de 23 est 1 dans toutes les bases,jusqu'a n-1.
    Voci le test de 91 .sachant que c'est un nombre composé.
    base a reste modulaire
    1 1
    2 64
    3 1
    4 1
    5 64
    6 64
    7 77
    8 64
    9 1
    10 1
    11 64
    12 1
    13 78
    14 14
    15 64
    16 1
    17 1
    18 64
    19 64
    20 64
    21 77
    22 1
    23 1
    24 64
    25 1
    26 78
    27 1
    28 77
    29 1
    30 1
    31 64
    32 64
    33 64
    34 64
    35 14
    36 1
    37 64
    38 1
    39 78
    40 1
    41 64
    42 14
    43 1
    44 64
    45 64
    46 64
    47 64
    48 1
    49 14
    50 64
    51 1
    52 78
    53 1
    54 64
    55 1
    56 14
    57 64
    58 64
    59 64
    60 64
    61 1
    62 1
    63 77
    64 1
    65 78
    66 1
    67 64
    68 1
    69 1
    70 77
    71 64
    72 64
    73 64
    74 1
    75 1
    76 64
    77 14
    78 78
    79 1
    80 64
    81 1
    82 1
    83 64
    84 77
    85 64
    86 64
    87 1
    88 1
    89 64
    90 1

  29. #24
    jean reaver

    Re : Nombres premiers et algorithme ?

    Si (mod)n est >1 ,alors est composé(corrig).

  30. Publicité
  31. #25
    jean reaver

    Re : Nombres premiers et algorithme ?

    A mon avis je pense qu'il y a une erreur d'incompréhension du théorème et
    moi j'ai fait cela.Tant qu'on parle de pseudo premiers !!!!
    Si o<a<(n-1) et pour tout a^(n-1) mod n =1,alors n est un nombre premier.

    input "test ";n
    for a=1 to (n-1)
    u=a^(n-1) mod n
    print a,u
    next a

    si chaque sortie égal à 1 : c'est premier .Tester de petit nombres.

  32. #26
    gg0

    Re : Nombres premiers et algorithme ?

    Oui, "'il y a une erreur d'incompréhension du théorème"; de ta part.

    Le théorème dit "si n est premier, ...". la réciproque est fausse.
    Et pour des petits nombres, il y a des algorithmes tellement plus rapides ...

  33. #27
    jean reaver

    Re : Nombres premiers et algorithme ?

    Avec a-a^(n-1)mod n=0 (n'est pas tout à fait le reciproque) .On générer tous les nombres premiers et les pseudo premiers.
    1
    2
    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
    341
    347
    349
    353
    359
    367
    373
    379
    383
    389
    397
    401
    409
    419
    421
    431
    433
    439
    443
    449
    457
    461
    463
    467
    479
    487
    491
    499
    503
    509
    521
    523
    541
    547
    557
    561
    563
    569
    571
    577
    587
    593
    599
    601
    607
    613
    617
    619
    631
    641
    643
    645
    647
    653
    659
    661
    673
    677
    683
    691
    701
    709
    719
    727
    733
    739
    743
    751
    757
    761
    769
    773
    787
    797
    809
    811
    821
    823
    827
    829
    839
    853
    857
    859
    863
    877
    881
    883
    887
    907
    911
    919
    929
    937
    941
    947
    953
    967
    971
    977
    983
    991
    997
    L'algo marche bien .L'erreur c'est les nombres carmichael dont le 561.
    Cet erreur revient au fait Que pour savoir si est premier ou non ,on doit tester dans tout base (a) jusqu'a (n-1).Par conséquent ,on passe les pseudos .JE sais que le reciproque est faux.
    a-a^(n-1)mod n=0 n'est pas le reciproque.

  34. #28
    jean reaver

    Re : Nombres premiers et algorithme ?

    Si la reciproque est fausse cela revient dire qu'on ne peut pas générer des prmiers.Ici ce n'est pas le cas.
    voir la liste que j'ai posté .

  35. #29
    ansset

    Re : Nombres premiers et algorithme ?

    ben , pourquoi insister, la réciproque est bien fausse puisque tu cites toi même les nombres de Carmichel !
    il n'a d'ailleurs pas démontré la réciproque, ce qui est bien normal.
    par ailleurs, Fermat l'a énoncé en 1640 ! ça fait un bail quand même.
    Il y a eu bien plus productif sur les nb premiers depuis.
    Dernière modification par ansset ; 08/09/2018 à 23h19.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  36. #30
    jean reaver

    Re : Nombres premiers et algorithme ?

    Sur 1000 nombres premiers ,en verifiant la liste :341;561;625 sont pseudo premiers.

Sur le même thème :

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. 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
  2. algorithme revolutionnaire des nombres premiers
    Par Guillaume Hawing dans le forum Discussions scientifiques
    Réponses: 0
    Dernier message: 15/09/2016, 11h00
  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