commence par faire un effort de compréhension en ce qui concerne "ton algo" et Eratosthène en expliquant la différence ...!Envoyé par akntn
ce n'est pas trivial c'est fantastique, tu viens de trouver la raison première des multiples de 239 999 999 983...et peux tu aller jusqu'au prochain carré, en gardant tous les entiers depuis 1 puisque tu en a besoin ...
Heureusement qu'Eratosthène ne s'est pas "em..." à écrire tous les multiples de chaque raison première...
Euh... À quoi sert la partie en gras ?Pour chaque entier n, il existe un et un seul diviseur d tel que n/d donne un premier si n est supérieur à d au cube.
'suffit de dire qu'il en existe un et un seul tel que n soit supérieur à d² (ajout qui ne sert que dans le cas où n=pq, p et q premiers)
Boah je me plante peut-être...
Et pis la découverte d'un théorème n'a rien de fantastique, il en sort des centaines (voire plus ?) chaque année...
Théorème : a+b ne peut pas être premier si a et b (>1) sont de même parité
Bonjour,
Pourquoi d^3 ? Parce que c'est la limite pour que n/d commence à ne donner que des nombres premiers.
Ex : pour le cycle 7, il faut attendre n > 7x7x7 (343) pour que les multiples de 7 ne donne que des premiers. En effet, pour 343, on a encore 343/7 = 49.
Pour le cycle 2, c'est évidemment beaucoup plus rapide (n > 2x2x2 ).
Un théorème est nécessaire pour expliciter une démarche mathématique. Ce théorème justifie mon algo. On peut évidemment s'en passer. On peut même se passer de mathématiques tout court.
Et même de culture.
Il me semble que l'on peut traduire la phrase précédente ainsi (je note \mathbb{P} l'ensemble des nombres premiers) :
Est-ce bien cela ? En fait je ne crois pas, parce que ceci est manifestement faux.
Serait-ce :
Et dans ce cas il serait intéressant qu'il soit démontré (c'est trivial) mais surtout il serait intéressant de trouver une borne inférieur à l'exposant (pourquoi 3 ?).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
bonjour,
tu penses sérieusement que si on se passe de ton algo c'est que l'on manque de culture et que dans ce cas on peut se passer des Mathématiques..?
il est vrai que ton algo est un très bon instrument de dissuasion pour les élèves qui veulent semer la pagaille en court..leur faire écrire ton algo jusqu'a 1000² et d'inscrire toutes les valeurs primaires manuellement, jusqu'à cette limite, çà devrait les calmer..
c'est plus efficace que la goutte d'eau.
Leg, je ne comprends pas ta susceptibilité. On dirait que je te gêne. Je te signale que j'ai fait confiance au forum, et je ne prétends pas imposer quoi que ce soit à quiconque. Il est parfaitement possible que mon algo soit nul ou simplement trivial. Et alors ? Ce qui compte avant tout, c'est l'échange.
Je ne vois pas l'intérêt d'utiliser cet algo jusqu'à 1000^2 ! Ce n'est pas un crible (un crible sépare les "premiers" et les "multiples", déjà expliqué). D'ailleurs, le crible lui-même est limité si on veut l'utiliser manuellement.
Médiat, je trouve ta deuxième expression compliquée (pour moi). Je ne vois pas en quoi la première serait fausse. J'ai expliqué pourquoi l'exposant 3. En deçà de n = d ^ 3, on n'a pas que des premiers si on divise n par d (par ex, si je divise 175 par 7, j'obtiens 25, qui n'est pas premier). Je suis d'accord pour démontrer ce théorème, mais pour l'instant j'en suis incapable.
n = 2 d = 2 vérifie
n = 2 d = 1 vérifie
donc d n'est pas unique.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
n = 2 d = 2 est impossible (dans cet algo).
Ce serait bien que tu te décides, au message #34 je dis qu'un certaine formule n'est sans doute pas ton théorème (car faux), au message 36 tu à l'air de dire que c'est bien ton théorème (car non faux), au message 37 je te montre qu'il est faux et au 38 tu dis que ce n'est pas ton théorème, donc, question prime-ordiale avant d'aller plus loin : Quel est ton théorème ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Bonjour
AKNTN
Un forum est fait pour des échanges, donc en aucun cas tu me gènes et je ne suis pas susceptible, loin de là; mais j'ai l'impression que tu ne te rends pas compte de certaine de tes remarques.
Plusieurs personnes ont fait l’effort de te conseiller de mettre ton travail pas à pas en vain; le début de ton message était sans équivoque, ce n'est que pour cela qu'il t'a été demandé de regarder ce qui existe, et par rapport à ton algo, est ce intéressant d'en tirer quelque chose..? Eratosthène te donne une très bonne occasion de comparer et d'exécuter les deux algo afin de te rendre compte ou se situe la différence, la simplicité, ne pas diviser, ne pas garder en mémoire des valeurs inutiles, ne pas avoir à s’occuper du prochain carré…etc
Les deux algo sont très simple, même à les écrire manuellement, et tu est bien obligé de te rendre compte quel est le plus simple à écrire. et éventuellement à utiliser.
J’ai fait l'effort de te mettre le début d'Eratosthène et uniquement modulo 9 afin de rester dans tous les entiers, mais il me semble que tu n'as pas compris...le fait de barrer des multiples ou de les entourer ou de les laisser sur une ligne à part ça ne change rien..car tu ne fait que la même chose en répétant tes premiers et en faisant des divisions et surtout en gardant en mémoires tous les entiers jusqu'au prochain carré et ainsi de suite ..
Exemple fait le jusqu'a 10² avec ton algo et Eratosthène tu es d’accord qu'avec ce dernier je n'ai quasiment rien à faire j'ai supprimé les 3 colonnes 3.6.9, rayé les 2n, et les terminaisons par 5 il me reste à compter qu'avec les premiers de 7 à 43 disons même <=31 puisque 43 va sur 86 et 37 sur 74…
Toi même tu reconnais tes limites alors soit simple et humble. Amicalement leg
Pourquoi un truc aussi simple suscite autant de malentendus ?
Différence entre Eratosthène et mon algo :
1) Eratosthène:
Le but est de séparer les "premiers" et les "multiples". Pour ce faire, je barre tous les multiples de n, de n en n, à partir de n^2.
Par ex (multiples de 3) :
9/12/15/18/21/24/27...
Si on prend cette suite, on constate qu'elle est périodique (elle n'est pas rangée selon la raison première). Et il en sera de même pour toutes les suites. Restent, évidemment, les premiers, puisqu'il s'agit d'un crible (on s'est débarrassé des multiples).
2) Mon algo :
Le but est de produire la raison première pour tout suite de multiples.
Pour ce faire, j'écris tous les multiples de n, de n en n, à partir de n^2, EN FONCTION DE TOUT CYCLE N > n.
Par ex (multiples de 3) :
9/12/15/18/21/27/33/39 ... (24 est impossible puisque "interféré" par le cycle 4, 36 est impossible puisque "interféré" par le cycle 6, etc.).
Cette suite de multiples de 3 est rangée selon la raison première à partir de 3x3x3. Et il en sera ainsi pour toutes les suites.
Si vous ne voyez aucune différence avec Eratosthène, je commencerai à douter de votre bonne foi.
Amicalement
alors surement qu'au niveau des suites il y a une légère différence, puisque dans l'exemple d'Eratosthène que j'ai montré il n'y a que des 0 dans les "cases" > 9 il n'est même pas question de s'occuper des périodes, on saute de Premier en Premier et on met des 1;
mais qui n'apporte rien à l'énumération des premiers et c'est de ça qu'il est question!
donc soit le fait de connaître la raison première, aurait un intérêt d'énumérer les premiers de façon plus simple qu'Eratosthène, pourrait donner l'envie de si intéresser, soit ce n'est pas le cas.
peux tu remplacer tout tes nombres > 9 par des 0.....?
pourquoi....?
est ce que le fait de connaître la raison première, permet d'énumérer tous les premiers dans l'ordre croissant, plus simplement q"Eratosthène ?
non ou oui pourquoi ?
et les malentendus viennent du fait que tu ne réponds pas aux questions qui te sont posées ...par les différents intervenants, et ce du simple fait, que tes formulations n'arrête pas de changer, Médiat à fait l'effort de te répondre ainsi que d'autre ...et alors .. ?
Bonjour,
D'accord avec toi Leg en ce qui concerne la meilleure efficacité du crible d'Eratosthène.
Cependant je rappelle que mon algo, même plus lent :
1° Ne supprime pas les multiples
2° N'utilise pas de tests de divisibilité
3° Enumère tous les multiples selon la raison première
C'est peut-être sans intérêt immédiat, mais c'est différent d'Eratosthène.
A Médiat : voici une autre version de mon "théorème", puisque la première version est "fausse".
Soit un entier n et un premier p.
Soit d le plus grand diviseur de n dont le carré est inférieur ou égal à n. Si n est supérieur à d^3, alors n / d = p.
Ex :
n = 68.
Plus grand d si d^2 < n : 4.
68 > d ^ 3 (= 64) alors 68 / 4 = 17 (premier).
Je rappelle que la suite des d (diviseurs primals) s'obtient grâce à mon algo.
Le problème suivant consiste à pouvoir calculer d pour n'importe quel entier. C'est évidemment très difficile, même si l'on sait que n est composé.
salut
on suppose
(1) d le plus grand diviseur de n dont le carré est inférieur ou égal à n
(2) n/d = a.b non premier, a <= b, n = d.a.b
(3) d^3 < n => a.b > d²
* si b > d
on doit avoir b > a.d car sinon :
(b <= a.d) => (b² <= a.d.b <= n) ce qui contredit (1)
et si on a : b > a.d, on a :
(a.d < b) => ( (a.d)² < a.d.b <= n ) ce qui contredit (1)
* si b <= d, on contredit (3) car sinon a.b <= b² <= d²
donc ton théorème est tout à fait vrai
le théorème en question étant bien sur :
Soit un entier n >= 2
Soit d le plus grand diviseur de n dont le carré est inférieur ou égal à n.
Si n est supérieur à d^3, alors p = n / d est premier.
Effectivement, si on écrit n/d=ab avec, alors, en partant de
Conclusion : n/d est premier > d .
bonjour
et si n < d^3 ...?
exemple de n =221
d² < n
d=13
soit n = 13*17
comment énumère t'on 221 selon la raison première.? ou du moins comment avec l'algo tu trouves 13, ou 17 puisque c'est le plus grand diviseur de n "directement";
Ou si ce n'est que de répéter tous les premiers < n jusqu'à n , et effectivement 13 ou 17 se seront placé sous 221,
"suivant le principe d'Eratosthène" ..
Merci à ACX et LEON pour les démos.
Si n < d ^ 3, n / d ne donne pas toujours un premier. Ton exemple :
n = 221
d = 13 (plus grand diviseur de n dont le carré est inférieur à n).
n/d = 17 (premier) mais c'est trivial. Il faut attendre n > 2197 (13x13x13) pour que n /13 commence à ne donner que des premiers.
L'algo donne d = 13 pour n = 221. Cela signifie que 221 appartient au cycle de 13, lequel débute à n = 169 (13x13). Le cycle "passe" en raison première au-delà de n = 2197, et d = 2197 / 13 (= 169). Autrement dit, le cycle de 13 donnera tous les premiers après 169 (d^2).
Pardon, pour n = 2197, on a toujours d = 13. C'est n/d qui est égal à 169 (d ^ 2).
On peut d'ailleurs commencer l'algo à partir de 13 x 13 (169). Pas nécessaire de tenir compte des cycles inférieurs à 13. On aura ainsi, à la longue, tous les NP > 169.
On ne retient que les n des cycles à partir de 13.
169 13
182 13
195 13
196 14
208 13
210 14
221 13
224 14
225 15
234 13
238 14
240 15
247 13
252 14
255 15
256 16
260 13
266 14
270 15
272 16
273 13
280 14
285 15
286 13
288 16
...
Evidemment, plus d est grand, plus l'écart entre d ^ 2 et d ^ 3 est grand. C'est la raison pour laquelle le crible d'Eratosthène est plus rapide.
Principe de l'algo :
1) Choisir un carré K1
2) Construire un cycle d (d = racine de K) jusqu'au carré K2 - 1
3) Ecrire les n correspondants
4) Construire le cycle d du carré K2 jusqu'au carré K3 - 1
5) Ecrire les n correspondants
5) Compléter avec les d inférieurs (du plus grand au plus petit)
Tous les cycles d (ainsi que les multiples n correspondants) adoptent la raison première lorsque n > d ^ 3 (ou n / d > d ^ 2).
