Algorithme nombres premiers

Fly77
Modifié (November 2023) dans Shtam
Bonjour.
J'aimerais savoir si mon algorithme est correct ?
Je ne suis pas certain de la justesse de l'algorithme car je l'ai trouvé par intuition et tâtonnement.
L'avantage de cet algorithme est d'avoir moins de nombres à cribler.
PS. J'ai arrêté les vérifications manuelles jusqu'à 211, 2310, ça commence à être fastidieux.
PS2. Je joins le fichier Office Calc qui m'a mis sur la piste.
PS3. Je ne souhaite pas ouvrir le débat sur le fait que $1\#=1$
[Il faut préciser que tu notes $x\#= \prod\limits_{\substack{p\leq x\\ p\text{ premier}}} p$. AD] 
$1\#+2=3$    J'arrête cet algorithmies dès que je dépasse $2\#$.

$2\#+3=5$
$2\#+5=7$   J'arrête cet algorithmies dès que je dépasse $3\#$.

$3\#+5=11$
$3\#+7=13$
$3\#+11=17$
$3\#+13=19$
$3\#+17=23$
$3\#+19=\textbf{25}$
$3\#+23=29$
$3\#+25=31$    J' arrête cet algorithmies dès que je dépasse $5\#$.
J’enlève les nombres de la forme $5^2+5k$.

$5\#+(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,\textbf{121},127,131,133,137,139,\textbf{143},149,151,157,161,163,167,\textbf{169},173,179,181,\textbf{187},191,193,197,199,203,\textbf{209},211)$    J'arrête cet algorithmies dès que je dépasse $7\#$.
J’enlève les nombres de la forme $7^2+7k$, $11^2+11k$, $13^2+13k$

Merci,
Thomas.

Réponses

  • LEG
    LEG
    Modifié (November 2023)
    Bonjour :
     A priori, c'est tout simplement une variante du crible d'Ératosthène ... en moins rapide .
     
    Tu pars d'un nombre premier $P$ et tu barres tous ses multiples : $P^2 + P*2k$ avec $k$ un entier naturel positif... Avec $P\leqslant\sqrt{n}$ et ensuite il te reste les nombres premiers $P\leqslant{n}$ ... Tu cribles tous les entiers impairs .... Pas moins.
  • Fly77
    Modifié (November 2023)
    Le crible d'Ératosthène cribble tous les nombres inférieurs à n qui ne sont pas premiers, ce qui en fait beaucoup.
    Par exemple, le nombre de nombres composés criblés avec la méthode d'Ératosthène inférieurs à 211 est de 163, hormis 1.
    Avec ma méthode, j'ai seulement éliminé 6 nombres composés : 25, 121, 143, 169, 187, 209.
    Ma liste a criblé est bien plus petite que n.
    De plus il n'est pas nécessaire de cribler de 4 jusqu'a n mais par exemple pour $5^2+5k$ seulement l’intervalle $3\#$  $5\#$

    Ma question est de savoir si cet algorithme oublie un nombre premier pour des nombres plus grands, voire s'il fonctionne jusqu'à l'infini, auquel cas l'algorithme fonctionne bien.
    Quant à savoir s'il est plus efficace que d'autres méthodes, je n'en sais rien.
  • gerard0
    Modifié (November 2023)
    Bonjour.
    Pour pouvoir répondre à tes questions initiales, il faut avoir
    * Le but de l'algorithme (bizarrement, tu as oublié d'en parler), dit précisément
    * L'algorithme lui-même, avec l'explication des notations non conventionnelles utilisées. "Je fais ci, je fais ça" sur des exemples n'est pas un algorithme.
    Cordialement.
    NB : Ma vieille version de Maple, sur un ordinateur d'il y a 10 ans, construit un tableau des 1000 premiers nombres premiers en 0,1 s.
  • lourrran
    Modifié (November 2023)
    @Fly77
    Regarde la page Wikipedia, elle explique le fonctionnement du crible d'Eratosthène. En particulier l'animation visuelle est sympa. Tu verras que c'est différent de ce que tu décris.

    Limite du Crible d'Eratosthène : on limite à l'avance le plus grand nombre qu'on a l'intention de traiter.

    Dans ton algorithme, quand tu pars par exemple de 5#, tu ajoutes des nombres qui par construction ne sont pas multiples de 5 ni de 3 ni de 2. Ok.
    Et si le résultat obtenu est multiple de d'un nombre premier ( multiple de 7, 11, 13 ...) tu le retires. Ok.
    Les nombres obtenus sont bien premiers.
    Obtiens-tu tous les nombres premiers ? Oui certainement.

    L'avantage de cet algorithme ... bof. Les nombres premiers ont été traités /étudiés dans tous les sens, par des gens qui ont testé des tas de choses, avec des nombres très grands. Et une 'amélioration' arriverait via une méthode qui n'a pas été testée au delà de 200 ??
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Merci lourrran Tu a répondu a ma question.
  • LEG
    LEG
    Modifié (November 2023)
    Fly77
    Je te répète , tu ne fais que cribler les entiers impairs , suivant le principe du crible Ératosthène mais en plus long ...

    Si cela 'amuses tu peux vérifier ...
    Ex $n = 731$ , $\sqrt{731} = 27,..$ , ok tu prends donc les nombres premiers  $P = (3,5,7,11,13,17,19,23)$

    Tu pars du carré de $P$ que tu marques en couleur, ou autre .. ainsi que  leurs multiples, par pas de $P$ ... les entiers impairs non marqués sont premiers, et tu réitères avec le nombres suivant qui n'est pas marqué ...  donc le prochain nombre premier $P$ . 
  • Fly77
    Modifié (November 2023)
    LEG
    Même en omettant les nombres pairs, la liste à cribler reste bien supérieure à la liste de mon algorithme.
    Mais comme l'a dit lourrran, qui lui a bien compris mon algorithme, l'avantage est bof.
    Pourquoi?
    Surement qu'il existe mieux!
  • LEG
    LEG
    Modifié (November 2023)
    Je pense que si tu connaissais vraiment ton algorithme, tu aurais remarqué que tu ne faisais que suivre le principe du crible Ératosthène d'où tu n'aurais pas eu besoins de poser ta question,  dont la réponse est évidente.

     Partir de P' au carré,  puis barrer tous ses multiples en rajoutant $P'k$  jusqu'à la limite $n$ que tu as fixé, avec $k$ pair...
    Tu peux expliquer ce qui est différent ...?
    À part le fait que tu fais des additions au lieu de progresser par pas de P jusqu'à la limite $n$ ce qui est plus rapide... Et tu retires (donc tu vérifies) les multiples de P > P' ; avec $P\leqslant\sqrt{n}$

    Ératosthène n'a nul besoins de faire ces vérifications ...
    Si tu sais programmer, tu verras très vite le résultat et la différence ...
    Il existe effectivement beaucoup mieux ... mais sans intérêt .
  • Bibix
    Modifié (November 2023)
    Bonjour
    Si j'ai bien compris l'algorithme, il retrouve tous les nombres premiers ssi $]p_n\#+1, p_n\#+p_{n+1}[$ ne contient jamais un nombre premier ce qui est évidemment vrai. Mais ça n'enlève qu'un ensemble négligeable d'entiers à tester (négligeable = de densité nulle).
  • Fly77
    Modifié (November 2023)
    Bibix
    Entre $13\#+1$ et $13\#+17$ il y a 3037 et 3041.
    Je ne comprends pas ce que tu veux dire.
    Ça veux dire quoi une densité nulle ?
    Qu'il y a quasiment aucun bénéfice de l'algorithme ?
  • Bibix
    Modifié (November 2023)
    Tu veux dire $30037$ et $30041$ ? $30037 = 7^2 \times 613$ et $30041 = 11 \times 2731$. La densité dans le cas particulier des entiers naturels (Dirac discrète) peut être définie par $\rho : A \in \mathcal{P}(\mathbb{N}) \longmapsto \underset{N \to +\infty}{\lim} \frac{{\rm Card}(A \cap [1, N])}{N}$. Par exemple, les ensembles des entiers pairs et impairs sont chacun de densité $\frac{1}{2}$.
    Cela veut dire que pour de très grands nombres, le gain de temps avec ton algorithme est négligeable.
    [Paul Dirac (1902-1984) prend toujours une majuscule. AD]
  • Fly77
    Modifié (November 2023)
    Bibix
    Ah oui excuse, j'ai oublié un zéro en cherchant.
  • LEG
    LEG
    Modifié (November 2023)
    Bonjour
    Bibix : je pense que sans aller très loin , En python par exemple et pour $n= 3000000000$ son algorithme mettra plus de temps que celui d'ÉRATOSTHÈNE  pour les entiers  naturels impairs , car il y a trop de "" va et vient "" et de vérifications ...

    Ce n'est que mon avis, car ce n'est pas par ce que l'on enlève quelques nombres impairs à cribler, que le programme serra plus rapide...même en supprimant les impairs multiples de 3 et 5 , c'est à dire en supprimant 73,3333...% des entiers naturels (multiples de 2 , 3 et 5 ).
  • @LEG C'est quoi, son algorithme selon toi ? Pour celui que j'ai compris à travers ses écrits, C'est faux. Une implémentation optimale du procédé de Fly77 est au moins aussi rapide que le crible d'Érathostène tout simplement car c'est une variante où on enlève des opérations à effectuer. D'ailleurs, la fin de ton commentaire est complètement fausse, évidemment. Tu n'as sûrement jamais pratiqué l'informatique sérieusement pour écrire de telles inepties.
  • @Bibix Moi je ne programme pas . Mais La personne qui m'a déjà fait ces programmes est pour le moins ... autant compétente que toi et elle sait de quoi elle parle  ...
    Si effectivement tu programmes , ne serait ce qu'en python , essaye donc pour une limite $N=4000000000$ temps mis et tu verras : si la fin de mon affirmation est fausse... 
  • Mais toi, tu ne sais pas de quoi tu parles. La preuve : tu n'as pas répondu à ma question :smile:
  • Bibix merci de ne pas parler comme ça à LEG, éminent mathématicien qui a prouvé la conjecture de Goldbach
  • J'trouve ça un peu LÈG.
  • Règle n°1 (rappelée par gerard0) :
    Pour parler d'efficacité d'un algorithme, il faut définir l'objectif. Recenser tous les nombres premiers inférieurs à 10000, ou recenser tous les nombres premiers inférieurs à 100000000, ce n'est pas la même chose. Un algorithme peut être très performant pour un des 2 objectifs, et très lent pour l'autre (voir incapable de fonctionner pour l'autre)
    Règle n°2 : 
    parler de nombres premiers avec LEG est impossible. Il considère que tout algorithme autre que le sien est forcément moins bien.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • LEG
    LEG
    Modifié (November 2023)
    La question est tout simplement une variante du crible Ératosthène .. qu'il construit en partant du carré de P ... si ce n'est comme l'a explicité Lourrran, sans le multiples de p' < P qu'il a déjà criblé ... et alors,  il va plus vite pour autant que le principe d'Ératosthène ...? C'est sans intérêt .

     Tu parles beaucoup ... mais tu n'essayes pas  au moins pour vérifier .... En python  ou en C++  ne te gène pas pour nous montrer... .

     En ce qui me concerne en C++ mon algorithme met 2,4 secondes pour cribler les nombres premiers > 5 et  inférieur à la  limite N  = 4 000 000 000 . Ton implantation optimal du procédé de  Fly77 met combien de temps ... Vas y ... mais pas en parlant .. !

    noobey :  je ne suis pas matheux et tout le monde le  sait sur ce site ... pourquoi : toi tu te prends pour un éminent matheux ? 
  • Python est 1000 fois plus lent que le C++ en moyenne. Ça ne te dérange pas si je fais le test en C++ seulement ? J'avoue, j'ai la flemme d'attendre 4h.
  • LEG
    LEG
    Modifié (November 2023)
    Pas du tout ..! Vas y en C++ par curiosité et par rapport à tes affirmations ... j'aimerai voir le résultat par pour son intérêt  bien entendu ... Mais au moins cela répondra à la question de FLY77 , qui n'est pas très convaincu... malgré tes explications et autres.

    @Lourrran comme à ton habitude tu n'es q'un menteur ... (ta règle n°2) Trouve moi où j'ai dit que mon  algorithme est meilleur que tout autre ! Je ne suis pas comme toi ...!

    Tu n'as qu'à regarder et essayer de comprendre l'algorithme (principe d'ÉRATOSTHÈNE)  construit par H Elfgott.
     Ou autres spécialistes en la matière ... 
  • lourrran
    Modifié (November 2023)
    @LEG
    Ta première réponse montre parfaitement ton comportement systématique, je cite : 
    A priori, c'est tout simplement une variante du crible d'Ératosthène ... en moins rapide .
    Un type pose une question, et tu lui dis que ce qu'il fait est nul. Avec des arguments qui sont factuellement faux.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • LEG
    LEG
    Modifié (November 2023)
    N'essaye pas de te justifier... toi tu dis que c'est nul 

    Moi je lui ai fait simplement remarquer, que c'est simplement une variante d'Ératosthène ... et en moins rapide. En quoi cela veut dire que son crible est nul ... et il pose une question afin de demander s'il crible tous les nombres premiers inférieur à une limite donnée. Ce qui veut bien dire que c'est le cas si il ne se trompe pas ... et il ne s'est pas aperçu que c'est une variante d'Ératosthène  sans les nombres pairs ...

    Maintenant il pense que c'est plus rapide qu'Ératosthène ... je lui dit  pour moi non ...!

    Car dans Ératosthène tu fixes ta limite N , tu n'est pas obligé d'écrire la liste des entiers impairs de 1 à N que tu vas cribler, (tu peux les représenter par des 1 et tu le remplaces par 0 , si multiple de P et en utilisant par exemple un index,  ...), tu connais le dernier nombre premier $\leqslant\sqrt{N}$ que tu vas utiliser  pour la fin du crible.

    Dans son cas et c'est pour cela qu'il a dit que pour 2310 c'est fastidieux ... :dizzy:
    Je suis presque persuadé qu'en utilisant ÉRATOSTHÈNE  manuellement on va pus vite..

    De plus son algorithme est faux (car dans sa méthode ""il dit"" qu'on enlève les multiples de 11 et de 13 de la liste des nombres < 211 . Ce qui est une erreur ... On enlève uniquement les multiples de 7, pour la cession suivante 7# = 210) jusqu'à 2310. (c'est simple à vérifier)

    Il est obligé d'écrire tous les entiers qu'il va cribler , enlever les multiples de $P^2 +Pk$, pour ensuite faire des additions afin d'écrire sa prochaine cession de nombres à cribler ... et à la fin : (enlever les multiples de 11.  .... tu parles d'un gain de temps... c'est le contraire .  )
    Au lieu de progresser par Pas de P ce qui est plus  rapide en programmation pour cribler de 11 à 13*2310 par exemple .

    Puis il recommence la prochaine cession sans les multiples de 11; avec la limite qui serra $2310*13 = 30030$  ... Il n'a pas fini d'en enlever des multiples de P > 11;   $P^2 +Pk$   à chaque cession :'(  

    Prouve  le contraire si tu te crois si malin, au moins il aura une réponse et non un bof ... qui ne veut rien dire (c'est peut-être ta façon d'enseigner ... ce qui serait étonnant.)

     Ta citation. Avec des arguments qui sont factuellement faux. En quoi c'est faux ? Ce n'est pas une variante d'Ératosthène en moins bien ?? Bibix s'est trompé ?

     Est-il plus rapide ... tu n'en sais rien !  Ta réponse a été : L'avantage de cet algorithme ... bof. Ça ça veut tout dire ...?
    Où tu es de mauvaise foi comme à ton habitude ... 

    Tu viens dans Shtam pour te croire intéressant ... fasse à des profanes ?? 
  • Fly77
    Modifié (November 2023)
    Salut.
    Je me suis rendu compte que l'algorithme que j'avais écrit oublie des nombres premiers.
    Je corrige donc avec une autre version.
    Avec cette méthode, il y a moins de nombres composés à cribler, mais je n'ai pas trouvé de méthode pour éliminer ces nombres composés.
    D'autant plus que même si je trouve une méthode, l'algorithme n'est pas performant selon les intervenants.
    $(2)+k(1\#)=(3)$ jusqu'a k=2-1

    $(3)+k(2\#)=(5,7)$ jusqu'a k=3-1

    $(5,7)+k(3\#)=(11,13,17,19,23,\textbf{25},29,31)$ jusqu'a k=5-1

    $(7,11,13,17,19,23,\textbf{25},29,31)+k(5\#)=(37,41,43,47,49,53,\textbf{55},59,61,67,71,73,77,79,83,\textbf{85},89,91,97,101,103,107,109,113,\textbf{115},119,\textbf{121},127,131,133,137,139,\textbf{143},\textbf{145},149,151,157,161,163,167,\textbf{169},173,\textbf{175},179,181,\textbf{187},191,193,197,199,203,\textbf{205},\textbf{209},211)$ jusqu'a k=7-1

    $(11,13,17,19,23,\textbf{25},29,31,37,41,43,47,49,53,\textbf{55},59,61,67,71,73,77,79,83,\textbf{85},89,91,97,101,103,107,109,113,\textbf{115},119,\textbf{121},127,131,133,137,139,\textbf{143},\textbf{145},149,151,157,161,163,167,\textbf{169},173,\textbf{175},179,181,\textbf{187},191,193,197,199,203,\textbf{205},\textbf{209},211)+k(5\#)=(221,223,227...\textbf{2303},2309,2311)$ jusqu'a k=11-1

  • LEG
    LEG
    Modifié (November 2023)
    Bonjour
    Effectivement, ton algorithme est loin de rivaliser avec ÉRATOSTHÈNE ... Mais cela te permet de comprendre pourquoi ... Afin de rivaliser avec Ératosthène...

    Ton algorithme avait une erreur avec ta méthode : on ne doit supprimer pour la cession suivante, par exemple la cession avec avec  7#  que les multiples de 7 et non ceux de 11 et de 13 de la liste établie avec 5# ;  $7,11,13,17,19,23,29,31+$ , k5# sans les multiples de 5 ... ! $(37,41,43,47,49,53,59,61)$ etc..
    Que tu réitères tous les 8 nombres avec $5\#\ = 30$., à la fin tu cribles les multiples de 7 pour la cession suivante ...etc etc 

    Tu aurais compris de suite pourquoi ce n'est pas efficace ... et pourquoi pour  $7\#\ = 210$ tu ne peux pas enlever les multiples de 11 et de 13 de ta nouvelle cession de [$11 , 13, 17 ,..., 203,209,211$] .sans les multiples de 5 et tu marques simplement les multiples de 7
    (
    que tu pourras utiliser ... )
    Ce que tu n'indiques toujours pas ...???


    Une méthode pour éliminer les nombres composés pour chaque nouvelle cession P# avec P > p' que tu viens de faire à la cession précédente , ("" sachant:
    Qu'à chaque nouvelle cession avec P# tu marques uniquement les multiples de P#  de la cession précédente..."") et ben  :D 

    Tu utilises les informations que tu as avec les multiples de P... OU :
    Tout simplement un petit programme d'Ératosthène  ou son principe... modulo 30 :D  :D
    Si tu avais un peu essayé la méthode du principe d'Ératosthène, tu ne te serait pas em..... pour rien...

    Amuse toi bien ... tu as suffisamment d'informations pour cribler efficacement ...
Connectez-vous ou Inscrivez-vous pour répondre.