yoshi
Salut,
Bonne nouvelle ! J'ai trouvé une méthode simple et j'ai optimisé mon code...
Pour le tri de 15000 nombres sur tes 3000 premières lignes, j'ai un temps, affichage compris, de 25 s (50 s pour 5000 lignes et 25000 nombres)...
2 5
0 3 7 0
11 13 17 19
0 23 0 29
31 0 37 0
41 43 47 0
0 53 0 59
61 0 67 0
71 73 0 79
0 83 0 89
0 0 97 0
101 103 107 109
0 113 0 0
0 0 127 0
131 0 137 139
0 0 0 149
151 0 157 0
0 163 167 0
0 173 0 179
181 0 0 0
191 193 197 199
0 0 0 0
211 0 0 0
0 223 227 229
0 233 0 239
241 0 0 0
251 0 257 0
0 263 0 269
271 0 277 0
281 283 0 0
0 293 0 0
0 0 307 0
311 313 317 0
0 0 0 0
331 0 337 0
0 0 347 349
0 353 0 359
0 0 367 0
0 373 0 379
0 383 0 389
0 0 397 0
401 0 0 409
J'ai testé tous les résidus possibles multiples de 7,11,13,17,19,23,29,31,37,41,43,47 : il n'y en a plus...
Ce n'est pas une preuve suffisante, mathématiquement parlant, mais mon algorithme se comporte avec ces tests ainsi que je l'attendais.
J'ai donc la certitude à 99,9 % d'être dans le vrai.
S'il y a des amateurs, pour chercher la faille, à vot' bon coeur... ;-)
@+
[supprimé]
Bonjour Yoshi
Je vous félicite pour votre travail et pour la bonne nouvelle
Ce que je voulais savoir est que vous pouvez faire la comparaison en temps avec le Crible d'Eratosthene dans les mêmes conditions?
Encore une fois BRAVO !!!
Lachkar
yoshi
Re,
C'est prévu. J'y réfléchis déjà.
Nouveau test : 10000 lignes, 50000 nombres --> 2 min 19 s. Ca reste raisonnable !
Les 3 derniers nombres 49991, 49993, 49999 sont bien premiers : testés avec
http://www.brennen.net/primes/FactorApplet.html
@+
[supprimé]
Salut
je vois que ça avance bien , mais il reste la comaraison entre les deux cribles
Salut
yoshi
Bonjour,
Mauvaise nouvelle et c'est tellement incroyable que je veux tout vérifier.
Eratosthène vainqueur par 4 à 0. AUtrement dit 22 s contre 1 min 28 s, pour 50000 nombres...
@+
[supprimé]
Bonjour
Si vous dite mauvaise nouvelle , c'est vraiment une ICROYABLE !
Il doit y avoir un hic quelque part
Bon courrage
Salut
Barbichu
Salut Yoshi,
et avec ce programme là pour eratosthène ? ça te donne quoi ?
(sachant que, sur ma machine la plus lente, il s'exécute instantanément sur l'entrée 50000 et mets 3s sur 500000)
def eratosthene(n):
nombres = []
premiers = []
for i in range(2,n+1):
nombres.append(True)
for i in range(2,n+1):
if nombres[i-2]:
premiers.append(i)
for j in range(2*i,n+1,i):
nombres[j-2] = False
return premiers
++
yoshi
RE,
9 s pour 50 000 000 de nombres....
Mais c'est pas réglo : il faut travailler comme on travaille à la main, sur une grille pré-remplie...
Je vais chercher à comprendre ce que fait ta fct exactement...
@+
Barbichu
Re,
Je travaille exactement comme à la main : le numéro de la cellule est le nombre (à 2 près), le contenu est le fait que ce soit barré ou non.
(True si non barré, False si barré (donc si non premier)). Et je n'ai pas besoin de regarder le nombre pour barrer : je raye une case sur i (pour i premier).
++
yoshi
Salut,
D'accord ! Mais ce que j'ai voulu dire c'est que tu ne stockes pas de nombres, que les booleens True,False.
Pour afficher tes nombres, il faut que j'affiche les indices de ta liste.
Cela dit, j'ai bien l'impression que travailler avec une liste de nombres qui se suivent à la queue leu leu, est plus simple et plus appropriée que de gérer un pseudo tableau avec un tuple, solution que j'ai employée.
Je vais réfléchir à modifier ma méthode de gestion du crible de Lachkar en fonction de ton idée : il sera moins lourd et moins gourmand en ressources de gérer et stocker True et False que nombres...
Je pense maintenant que, au moins informatiquement parlant, la méthode de Lachkar ne pourra lutter en vitesse contre le crible d'Eratosthène...
@+
Ps Connais-tu un tuto clair expliquant, pourquoi et quand créer des classes en Python (et accessoirement ce qu'elles peuvent gérer ou pas) : le bouquin de Swinnen dont on fait tant de cas est plein de non-dits...
Tu peux répondre par mél...
[supprimé]
Bonsoir
Je suis vraiment trés déçu ,moi qui avait pensé avoir trouver un crible trés facile, j'espèce que vous aller trouver la solution.
Autre chose,
Mon idée à moi c’était de dresser des colonnes ou sont inscrits 5 différents types de terminaisons des nombres.
Pour chaque colonne la terminaison est
Colonne 1 ; 11 , 21 , 31 ,41….
Colonne 2 ; 13 , 23 , 33 , 43…..
Colonne 3 15, 25 est à éliminer
Colonne 4 ; 17 , 27 , 37 , 47 …….
Colonne 5 ; 19 , 29 , 39 , 49….
La raison pour passer d’un nombre à l’autre est de 10
Je pensais qu’on pouvait faire une programmation facile colonne par colonne.
Si nous dressons la colonne 1 sous cette forme en 8 colonnes et n lignes
Nous pouvons éliminer facilement les multiples de 3 (21 51 ) en diagonale de gauche vers la droite et les multiples de 7 (21 231 ) de droite vers la gauches.
1 11 21 31 41 51 61 71
81 91 101 111 121 131 141 151
161 171 181 191 201 211 221 231
241 251 261 271 281 291 301 311
321 331 341 351 361 371 381 391
401 411 421 431 441 451 461 471
481 491 501 511 521 531 541 551
561 571 581 591 601 611 621 631
641 651 661 671 681 691 701 711
721 731 741 751 761 771 781 791
801 811 821 831 841 851 861 871
881 891 901 911 921 931 941 951
Salut
Lachkar
[supprimé]
Bonjour Yoshi,
je vois que vous avait laissé tomber vos recherches , en ce qui concerne le crible de Lachkar, est ce que vous êtes certains que ce crible ne peut pas concurrencier celui d'Eratosthene.
Je crois qu'avec un peu de perseverence ,il y a certainement une solution et un défi à ce crible.
salut
yoshi
Bonsoir,
Non, je n'ai pas vraiment abandonné, j'attends qu'une "idée me trouve"...
M. Lachkar, dans un programme informatique, ce qui ralentit le traitement des informations, ce sont les tests : ces instructions qui commencent par : if...
Si vous regardez bien le petit programme de détermination des nombres premiers de Barbichu (#87 ) par la méthode du crible d'Eratosthène, il n'en contient qu'un seul : 9 s pour le test des 5000000 premiers nombres...
Très très difficile de faire mieux ! Il faudrait pour ainsi dire n'en utiliser aucun ! Mission impossible.
Cela dit, l'informatique, pour une fois, ne rend pas justice à votre crible : je suis persuadé qu'avec un papier et un crayon, il est au moins aussi rapide que celui d'Eratosthène...
@+
[supprimé]
Bonjour
Dans mes écrits j'ai touvé une relation à moi que j'avais établit entre la somme des diviseurs d'un nombre impair et le nombre en question.
Nous savons que un nombre pair est parfait si la somme de ses diviseurs lui est égale.Alors que pour un nombre impair il n'en existe pas.
Ma relation à moi est la suivante
Comment on peut appeler un nombre impair si
la somme de ses diviseurs est égale au tiers de ce nombre plus 4
Salut
yoshi
Bonsoir,
J'ignore s'ils portent un nom...
Pour les noms nommés aux nombres : abondants, déficient, parfaits, etc...
Voir notamment
http://fr.wikipedia.org/wiki/Nombre_abondant
ou encore :
http://villemin.gerard.free.fr/Wwwgvmm/Decompos/SixNbPf.htm
Il me semble ce genre de classification a commencé avec Pythagore (à vérifier).
@+
[supprimé]
Bonjour Yoshi
Merci pour les renseignements, j'ai dèjà regardé sur ces sites,mais j'ai rien trouvé en ce qui concèrne mon idée qui est relatve à la relation entre un nombre impair la somme de ses diviseurs.
Salut
[supprimé]
Bonjour
Je reviens à cette histoire des nombres premiers et cette fois-ci avec mes carrés "" imagiques""
dressons un tableau de (n,n) ou on inscrit
sur la première ligne de n colonnes les chiffres 2 - 3 - 4 - 5 - ...
sur la deuxième ligne les carrés des nombres de la 1ère ligne
sur la 3ème ligne le cube de la première ligne
et ainsi de suite pour les autres lignes.
prenons par exemple un carré de 3x3 dont son centre est le carré de 3 qui est neuf d'ou on a
2 3 4
4 9 16
8 27 64
si on fait la sommation du nombre de centre 9 avec les nombres des coins on obtient des nombres premiers
9+2=11
9+4=13
9+8=17
9+64=73
prenons le carré ayant pour centre le carré du nombre 5 qui est 25
4 5 6
16 25 36
64 125 216
25+4=29
25+6=31
25+64=89
25+216=241
j'ai d'autres carrés "imagiques" et je laisse à ceux qui s'interessent de chercher d'autres combinaisons
pour le mot "imagique" je ne sait pas d'abord est ce que une telle forme existe+t+elle ou non
Salut
Lachkar M.
Golgup
Salut,
C'est quand même fou! les coïncidences!
Il ya de cela 4 jours, je remarquais que n^2 + n-1 donnait souvent des nombres premiers, celle ci est directement liée avec tes tableaux! Mais il ya plein de contre exemples..
A+
[supprimé]
Bonjour
C'est vrai qu'il y a plein de contre exemple, c'est pour cela qu'il faut dénicher les cas qui peuvent aboutir à des nombres premiers.ceci dit.
Maintenant j'ai autre chose à dévoiler
Nous savons qu'un nombre pair parfait est celui dont la somme de ses diviseurs lui y est égale, par contre les nombres impairs ne répondre pas à cette relation.
Moi je propose la relation ci-dessous qui relait la Somme des diviseurs de ce Nombre et le Nombre impair
soit les relations
N = 45 K – 6 = 3( 4^2 - 1 ) K - 6
N
et S = ------ + 4
3
pour tous K impair
on peut dire que un nombre est parfait impair si
N = S + 2( N/3 - 2 )
pour tout nombre se terminant par 9
39 = 17 + 2( 39/3 -2 ) =17 + 22 = 39
759 n'est pas parfait car :
393 + 2 ( 759/3 -2 ) = 393 + 502 =895
pour les autres terminaisons il y a un petit changemant dans la formule.
---------------------------------------------------------------------
K N Diviseurs S
1 39 1;3,13 17
3 129 1; 3,43 47
5 219 1; 3,73 77
7 309 1; 3,103 107
9 399 1; 3,133 137
11 489 1; 3,163 167
13 579 1; 3,193 197
15 669 1; 3,223 227
17 759 1,3,11,23,33,69 393
On peut dire que SI la somme de diviseurs d’un nombre impair est égale au tiers de ce nombre plus 4, et si on divise ce nombre N uniquement par 3, alors le nombre trouvé sera premier.
Salut
Lachkar M
[supprimé]
ouah, vous êtes un peu des savants fous, ici. Futurs Euler, Fermat, Mersenne, je vous salue !
je n'irai pas aussi loin, je me demandais juste s'il y avait un moyen de faire un tableau du crible d'eratosthene (pas celui de lachkar, même s'il a l'air très bien, mais c'est pas vraiment dans le vif de mon sujet) avec LaTeX (sans écrire puis barrer les nombres à la main). écrire une commande qui me calcule tout ca tranquillement.
(sinon j'insèrerai une image mais c'est pas très classe)
merci pour votre aide !