Algorithme nombres premiers
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\#$.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]
$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
-
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. -
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.
-
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. -
@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
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
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$ . -
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 . -
BonjourSi 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).
-
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] -
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
-
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
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
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.
-
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 ... -
@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
L'hypocrisie est pire qu'une vérité qui fait mal. Franck Ntasamara. -
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 ...
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 ?? -
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
-
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
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
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.
Bonjour!
Catégories
- 165.6K Toutes les catégories
- 64 Collège/Lycée
- 22.2K Algèbre
- 37.7K Analyse
- 6.3K Arithmétique
- 61 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 26 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.8K Géométrie
- 86 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 29 Mathématiques et finance
- 343 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.4K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 804 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres