Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 20-05-2017 09:37:32

Margaillan Victor
Membre
Inscription : 20-05-2017
Messages : 3

Crible d'Ératosthène sexy

Bonjour
Il a quelques mois j'ai trouvé un petit truc amusant pour améliorer le crible d'eratosthène je sais pas si ça existe déja
mais je vais essayer d'étre clair (je suis pas très fort en math) ça part de cinq postula :

-1 que les nombres premiers sont en deux groupes
-2 que ses nombres sont une suite par 6 des deux nombres premiers 5 et 7 avant criblage
     (ex: 5+6=11+6=17+6=23ect...7+6=13+6=19+6=25ect...)
-3 ont laisse de coté 2 et 3 et leurs multiples
-4 pour cribler ont va utiliser que des nombres premiers a partir de leurs carré (ex: 7²=49; 11²=121; 13²=169 ect...)
    puis ont va les multiplier avec les nombres premiers qui leurs sont supérieur (ex: 7x11=77; 7x13=91 ect... 11x13=143;11x17=187 ect...)
-5 bien entendu on enlève tout les multiples de cinq

après ils y a encore quelques règles mais ça vas venir le mieux c'est un exemple :

le groupe de 5

5,11,17,23,29,35,41,47,53,59,65,71,77,83,89,95,101,107,113,119,125,131,137,143,149,155,161,167,173,179,185,191,197,203,209 ect...

le groupe de 7

7,13,19,25,31,37,43,49,55,61,67,73,79,85,91,97,103,109,115,121,127,133,139,145,151,157,163,169,175,181,187,193,199,205,211 ect...

Ont va déja  enlever tout les multiple de cinq:

5,11,17,23,29,41,47,53,59,71,77,83,89,101,107,113,119,131,137,143,149,161,167,173,179,191,197,203,209 ect..
7,13,19,31,37,43,49,61,67,73,79,91,97,103,109,121,127,133,139,151,157,163,169,181,187,193,199,211 ect...

là on commence avec 7: 7²=49;7x11=77;7x13=91;7x17=119;7x19=133;7x23=161;7x29=203 ect..

5,11,17,23,29,41,47,53,59,71,83,89,101,107,113,131,137,143,149,167,173,179,191,197,209 ect..
7,13,19,31,37,43,61,67,73,79,97,103,109,121,127,139,151,157,163,169,181,187,193,199,211 ect...

puis avec 11: 11²=121;11x13=143;11x17=187;11x19=209 ect...

5,11,17,23,29,41,47,53,59,71,83,89,101,107,113,131,137,149,167,173,179,191,197 ect..
7,13,19,31,37,43,61,67,73,79,97,103,109,127,139,151,157,163,169,181,193,199,211 ect...

avec 13: 13²=169;13x17=221 ect..

5,11,17,23,29,41,47,53,59,71,83,89,101,107,113,131,137,149,167,173,179,191,197 ect..
7,13,19,31,37,43,61,67,73,79,97,103,109,127,139,151,157,163,181,193,199,211 ect...

avec 17 et ainsi de suite avec tous les nombres premiers.

normalement il y a tous les nombres premiers de 5 a 211 dans la dernière suite et sans intrus
voila voila

Hors ligne

#2 20-05-2017 13:10:13

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 907

Re : Crible d'Ératosthène sexy

Bonjour,

Bienvenue chez nous !

J'ai déjà pas mal bidouillé pour améliorer la vitesse du crible...
Déjà, éliminer les multiples de 2 et 3, c'est une bonne idée...
Ensuite tous les nombres premiers sont du type 6k+1 ou 6k+5, où k est un nombre entier quelconque supérieur à 0...
Pourquoi ?
6k = 2 x 3 x k est un multiple de 2 et de 3 : à éliminer.
6k+2 = 2(3k+1) est un nombre pair : à éliminer.
6k+3 = 3(2k+1) est un multiple de 3 : à éliminer.
6k+4 = 2(3k+2) est un nombre pair : à éliminer.
6k+6 = 6(k+1) est un multiple de 2 et de 3, donc à éliminer.
6k+1         6k+5
  7              11
13              17
19              23
25              29
31              35
37              41
43              47
49              53
55              59
61              65
67              71
73              77
79              83
85              89
91              95
97             101
103             107
109             113
115             119
121             125
127             131
133             137
139             143
145             149
151             155
157             161
163             167
169             173
175             179
181             185
187             191
193             197
199             203
205             209
211             215
Dans ces listes, il n'y a pas non plus de multiple de 5 avant 25, de multiple de 7 avant 49, de multiple de 11 avant 121... etc
J'ai un crible qui fonctionne comme ça et avec quelques détails supplémentaire
s.
http://www.bibmath.net/forums/viewtopic.php?id=9001
Je testerai (en programmant) ta suggestion quand j'aurai un peu de temps et je verrai si tu es plus rapide que "mes bidouilles"...

@+


Arx Tarpeia Capitoli proxima...

En ligne

#3 23-05-2017 12:11:48

Margaillan Victor
Membre
Inscription : 20-05-2017
Messages : 3

Re : Crible d'Ératosthène sexy

oui il sont un peu identique le groupe de cinq sont les 6k+5 et le groupe de 7 les 6k+1
par contre pour cribler j'utilise le cycle de chaque nombre premiers qui je ne sais pas pourquoi ne se croise jamais
et je n'ai pas compris pourquoi les carres de nombres premiers sont toujours des 6k+1

Hors ligne

#4 23-05-2017 13:37:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 907

Re : Crible d'Ératosthène sexy

Bonjour,

Si un nombre est premier c'est forcément un 6k+1 ou 6k+5 (L'inverse n'est pas vrai, tous les 6k+1 ou 6k+5 ne sont pas premiers).
Cas d'un premier de la forme 6k+5
  [tex](6k+5)^2=36k^2+60k+25= 36k^2+60k+24+1=6(6k^2+10k+4)+1[/tex] c'est bien un 6k'+1, et c'est même un multiple de 12 plus 1 :
  [tex](6k+5)^2=12(3k^2+5k+2)+1[/tex]

Cas d'un premier de la forme 6k+1
   [tex](6k+1)^2=36k^2+12k+1=6(6k^2+2k)+1[/tex] c'est bien un 6k'+1, et c'est même lui aussi un multiple de 12 plus 1 :
   [tex](6k+1)^2=12(3k^2+k)+1[/tex]

Donc, toujours vrai.

@+


Arx Tarpeia Capitoli proxima...

En ligne

#5 07-08-2017 06:40:38

frangipane
Invité

Re : Crible d'Ératosthène sexy

Bonjour,

Oui à part 2 et 3 un nombre premier est forcément un 6k+1 ou 6k-1 (qu'on dise +5 ou -1 devrait être équivalent ^^ avec k > 0)
Ce que j'ai remarqué c'est qu'un nombre de la forme 6k-1 qui n'est pas premier est forcément un produit d'un 6k-1 par un 6k+1, par contre 6k+1 est soit le produit de 6k+1 soit 6k-1 (l'un OU l'autre, et pas l'un et l'autre, c'est pour ça que dans un autre sujet je disais qu'une forme de facteur de nombre était 2 fois plus facile à trouver qu'un autre! C'est une image mais bon, dans un cas on peut tester seulement les 6k-1 (ou +1) mais dans l'autre cas on doit forcément tester les 2 formes)

Evidemment je prend en compte les facteurs les plus élevés pour les nombres qui pourraient avoir plus de 2 facteurs à un certain point.

Dernière modification par yoshi (07-08-2017 08:51:30)

#6 12-08-2017 14:50:12

LEG
Membre
Inscription : 19-09-2012
Messages : 690

Re : Crible d'Ératosthène sexy

@Frangipane
ton raisonnement est faux, car pour tester un nombre quelque soit sa forme , 6k+1 ou 6k-1 cela revient à trouver le premier facteur P , < à la racine carrée de ce nombre, et il serra de la forme 6k+1 ou 6k-1 donc pas plus facile à trouver sauf si le premier facteur P est proche des premiers nombres premiers.... mais à taille égale du premier facteur P et bien.....tout aussi difficile ......

Il y a quand même autant de nombres premiers de la forme 6k+1 que 6k-1 .

ex : n = 246157 = 6k-1 ; et m = 241788 = 6k+1

facteur P < sqrt de n ou m = 1567 = 6k+1  ;

la difficulté ne vient pas de la forme 6k+1 ou 6k-1 mais de sa structure....c'est pour cela qu'il existe des algorithmes de factorisation très sophistiqués comme par exemple sur le site de Alpertron ....etc...

Car certains grand nombres se factorisent  assez vite, et d'autres prennent des mois.....

Hors ligne

Pied de page des forums