[Python]Erathostene, paris ouverts

Réponse 1 / 15

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
23 juin 2003 à 09:03

Etant donné qu'à l'infini le nombre de nb premiers est de l'ordre de log(n)/n, et que je crois me souvenir que j'avais passé une nuit (en C++) à récupérer le premier million ;p.

J'ai peur que ça ne te prenne bcp de temps ;p. Et pis, je vais ptete faire bondir sebsauvage, mais je ne sais pas si le python est le langage adéquat pour des calculs de ce type... C quand meme un langage interprété, non ?

Idée : tu pourrais pas faire que tous les n nb trouvés, ton prog te fasse un log ? tu pourrais ainsi savoir s'il avance et à quelle vitesse à peu près .

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
23 juin 2003 à 09:18

Je changerais peut etre ca pour le lancer le week end prochain :o)
En fait mon but n'est pas d'effectuer les calcul mais bien de tester python, sinon les nombres premiers, je trouve ca plus rigolo que les factorielles (d'ailleurs il est precis pour les factorielles, c'est le 2eme langage que je rencontre qui marche aussi bien pour ca).

. .
\_/

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 10:06

log(n)/n me parait louche quand meme au vu de mon retour sur 100000: 9562 premiers, hors log(n)/n=0,000005 :-DDDDD
Ca serait aps plutot n/log(n)=20 000? Voire n/ln(n)=8686 ou n/2log(n)=10 000?

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
25 juin 2003 à 11:27

Non c'est une approximation, comme je l'ai dit c'est une idée d'ordre et non de calcul précis (un peu comme pour la complexité d'un algo) mais ce n'est surtout pas n/log(n) :-)

=> c'est le nombre de nbs premiers à l'infini

C'est simple à comprendre : plus le nombre est grand, moins il a de chances d'être premier. Tout simplement parce que plus il est gd, plus il a de chances de trouver un diviseur...

Tu peux aussi t'en apercevoir en faisant la moyenne des écarts dans les "tranches" de nbs : du 1 au 10 nb premier du 10eme au 20eme (tiens faudrait que je le fasse ce calcul : si tu le fais les résultats m'intéressent ;p), etc. les écarts grandissent en fonction du n (évident).

n/log(n) => à l'infini la croissance de n est beaucoup plus gde que log(n), donc non ;p

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793 > batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008
25 juin 2003 à 11:39

Je sais bien ce qu'est l'infini, mais ce qui est valable pour l'infini est approximativement valable pour les grands nombres, et 100 000 on s'approche des grands nombres...
Le probleme c'est que log(n)/n-> 0 quand n-> inf (ben oui, la croissance de n est superieure a celle de log(n) hors le nombre de nombres premiers ne peut etre que croissant....

Donc (je viens de demander confirmation a un collegue docteur en math specialise dans l'arithmetique) c'est bien l'ordre de grandeur de n/log(n)

Et meme google s'y met:

http://mathworld.wolfram.com/PrimeNumberTheorem.html

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
25 juin 2003 à 11:49

Je me suis mal exprimé : c'est d'ailleurs ce que j'ai cherché à dire plus haut : le nombre de premiers par intervalles est de cet ordre.

Pas le nb de premiers dans l'absolu, bien sûr. Je suis tout à fait d'accord pour dire qu'il existe une infinité de nombre premiers ;p

Pour finir, clarifier et résumer ce que je voulais dire : l'écart en le nieme et le (n+1)ieme nombre premier grandit toujours en fonction de n. Et pour les gds nombres l'écart en devient d'autant plus gd. (d'où le temps de calcul exponentiel pour trouver un gd nd qui ne soit pas que pseudo-premier)

@++
Poster, poster encore et toujours :-)

Réponse 2 / 15

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
23 juin 2003 à 09:06

1) Autre chose : une question bête, mais primordiale : quand tu testes un nombre n, j'espère que tu testes les nombres inférieurs ou égaux à racine(n) seulement et pas au delà

2) Pour info, mon prog avait tourné toute la nuit, mais je ne testais pas TOUS les nombres en dessous : je ne testais que les nombres premiers inférieurs ou égaux à la racine (voir ci-dessus) que j'avais précédemment trouvé... Ca aussi, c'est un gain de temps importants : on ne teste plus tous les nombres impairs mais seulement ceux qui sont premiers :)

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
23 juin 2003 à 09:20

Ben en fait, je teste les multiples (jusqu'a la limite de mon tableau) et je les vires donc quand j'arrive sur un nombre il est forcement premier :o)
Mais c'est vrai qu'il y a de la place pour optimiser encore, j'ai fait ca vendredi une heure avant de partir et j'ai commencer mon premier "programme" en python quelques heures avant donc forcement ;-)

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 09:29

Tu t'arretes bien à la racine ?

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 09:52

Ben non, comme je le disais c'est pas optimiser, mais je ne prend pas au dessous, je prend au dessus je fais le crible pas la methode de je ne sais plus qui:


1 2 3 4 5 6 7 8 9 10

Passer le 1

Traiter 2:

1 2 3 5 7 9

Traiter 3:

1 2 3 5 7

Traiter 5

1 2 3 5 7

Traiter 7

1 2 3 5 7  <-Resultat

. .
\_/

Réponse 3 / 15

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
23 juin 2003 à 09:09

gain de temps importants
précédemment trouvés

Désolé :) normalement, je me relis ...

@++
Poster, poster encore et toujours :-)

Réponse 4 / 15

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
23 juin 2003 à 09:36

Ya un type natif pour les gds entiers ?

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
23 juin 2003 à 09:52

Je ne sais pas, apparement il n'y a pas de types en python (au moins en delcaration...)

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 10:37

En fait, ce que je veux dire c'est : est ce qu'il ya une limite sur les entiers. Je sais que le typage est dynamique en python mais je me demande ce qu'il se passe si on additionne ou multiplie des très gds nombres : ça boucle ou ça s'adapte ?

@++
Poster, poster encore et toujours :-)

Réponse 5 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
23 juin 2003 à 10:38

Ca s'adapte :o)
J'ai eu le resultat vrai de 100000! (plusieurs page l'entier :-D)

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
23 juin 2003 à 11:03

Euuu Teebo, je comprends po ta phrase ;p. comment ça :-D
>resultat vrai de 100000 ?!?

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
23 juin 2003 à 11:06

Ben il y a pas mal de langage qui bouclent et donc tu as eventuellement un resultat negatif, le ! n'est pas de la ponctuation mais un operateur mathematique (factoriel, au cas ou: !x= x*(x-1)*...*3*2*1) :o)

. .
\_/

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 11:21

Oui oui, je connais le principe du bouclage...

Tu parlais en fait de !100000, c'est ça ? Tu voulais dire que le résultat était ok et faisait plusieurs pages (soit dit en passant, comment t'as fait pour vérifier qu'il était bon ? tu t'es amusé à le faire à la main ? :) )

@++
Poster, poster encore et toujours :-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 11:44

Oui mais moi je le note a la fin, on m'a toujours appris comme ca :o)
Sinon ben j'ai teste en Smalltalk et j'ai compare :o)

. .
\_/

Galfus Messages postés 242 Date d'inscription lundi 19 mai 2003 Statut Membre Dernière intervention 8 novembre 2008 14 > teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011
23 juin 2003 à 12:21

hé les gars, vous n'avez pas mal à la tête ?

<------Galfus------>
In penguin we trust

Réponse 6 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
24 juin 2003 à 17:44

A plus de 90h, j'ai craque :-S

. .
\_/

Réponse 7 / 15

sebsauvage Messages postés 32893 Date d'inscription mercredi 29 août 2001 Statut Modérateur Dernière intervention 21 octobre 2019 15 655
24 juin 2003 à 17:58

Quelques questions:

Ton tableau, il est de quel type ? liste, tuple ou dictionnaire ?

Quelle version de Python utilises-tu ?
(La 2.3 est censée avoir des amélioration questions perfs).

As-tu pensé à utiliser psyco ?
Chez moi ça fait des merveilles.
http://psyco.sourceforge.net

et ajoute:

import psyco

psyco.full()

au début du programme.

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
24 juin 2003 à 18:01

C'est une liste, j'ai deja du fighter au debut parce que je comprenais pas tout :o)
La version est la 2.2.2 sous windows

J'ai pas pense a utiliser Psyco, et pour cause :-D Merci pour le lien ;-)

. .
\_/

Réponse 8 / 15

sebsauvage Messages postés 32893 Date d'inscription mercredi 29 août 2001 Statut Modérateur Dernière intervention 21 octobre 2019 15 655
24 juin 2003 à 17:58

PS:
Je crois qu'il y a des algos plus performants que le crible d'Eratostène.

PS2:
Il y a des optimisations possible sur ce crible. ;-)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
24 juin 2003 à 18:02

PS1: Possible, j'avoue que je ne me souviens plus bien de tout cela

PS2: Oui ca c'est sur, mais j'ai deja eu tellement de mal avec mes debuts en python, en fait c'est vachement vaste et je me retrouve vite perdu pour le moment :o)

. .
\_/

Réponse 9 / 15

sebsauvage Messages postés 32893 Date d'inscription mercredi 29 août 2001 Statut Modérateur Dernière intervention 21 octobre 2019 15 655
24 juin 2003 à 18:46

no soucy.

Pense à jeter un coup d'oeil sur le wiki, il y a quelques exemple sympas.
http://wikipython.tuxfamily.org

Sinon n'hésite pas à demander.

ah... et jette aussi un coup d'oeil à certaines particularité de Python, comme les tuples, listes, dictionnaires et les 'list-comprehension'. ça fait des merveilles.
(voir chapitres 1.7, 1.8 et 1.9 là :http://diveintopython.org/odbchelper_divein.html)

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 09:05

Merci pour les liens :o)
J'avais deja trouve DiveInto mais Wiki je ne connaissais pas...

. .
\_/

Réponse 10 / 15

batmat Messages postés 1871 Date d'inscription jeudi 1 novembre 2001 Statut Membre Dernière intervention 9 janvier 2008 114
24 juin 2003 à 18:52

Je te proposerai bien mes services en terme de calculs de nb premiers ;p Mais je crois que tu as déjà dit que ton but premier était plutot l'apprentissage du python :)

@++
Poster, poster encore et toujours :-)

Fu Xuen Messages postés 3639 Date d'inscription jeudi 24 avril 2003 Statut Contributeur Dernière intervention 11 septembre 2005 305
24 juin 2003 à 21:00

Ça n'empêche qu'un rappel des algorithmes - heuristiques je crois - couramment utilisés pour déterminer le caractère premier d'un nombre pourrait être très intéressant, toute digression excessive mise à part :).

-= Fu Xuen =-

Fu Xuen Messages postés 3639 Date d'inscription jeudi 24 avril 2003 Statut Contributeur Dernière intervention 11 septembre 2005 305
24 juin 2003 à 22:32

Pour ceux que ça intéresse, Google est notre ami : [http://www.haypocalc.com/maths/algo_premier.php] et [http://www.utm.edu/research/primes/prove/index.html].

-= Fu Xuen =-

Réponse 11 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 09:10

Oui en effet, je m'en fout un peu (a part la curiosite) de trouver tous les nombres premiers jusqu'a 10 millions :-D
Merci Fu-Xuen pour les liens, quelques rappels sont toujours sympa :o) Mais je persiste a vouloir implementer le crible qui me parait la meilleure solution :o)

. .
\_/

Réponse 12 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 10:28

Bon, je viens de faire le test opur 100 000 avec et sans psyco, resultat quelques secondes (11) de gagnees sur 6 minutes environ, rien de bien transcendant mais bon le programme est pas bien long en lui meme...

Bon, je vais lancer un gros pour voir si j'ai bien optimiser maintenant en partant en week end, mais en attendant, j'arrete de faire joujou avec eratosthene :o)
Merci a tous :o)

. .
\_/

sebsauvage Messages postés 32893 Date d'inscription mercredi 29 août 2001 Statut Modérateur Dernière intervention 21 octobre 2019 15 655
25 juin 2003 à 11:00

Pour Psyco, c'est très variable, mais généralement l'amélioration des perfs est bien meilleure.

Sinon pour le crible d'Eratostène, je ne pense pas que ça soit spécfiquement dû à Python. Ce genre de calcul est monstrueux sur 10 000 000 :-)

Tant que j'y suis, j'ai mis en ligne hier quelques exemples de code Python (en vrac):
http://sebsauvage.net/python/snyppets/
(ça fait un peu doublon avec le wiki, mais je voulais mettre ça en anglais, et certains trucs me semblaient mal entrer dans le wiki)

Réponse 13 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 11:05

Merci :o) Maintenant je joue avec les grabscreen mais j'arrive pas a prendre mes deux ecrans :-S

C'est a toi Wiki?
Sinon, pourquoi tu fais pas un site "Python Sauvage"? Desole, la porte est par la ==================>

. .
\_/

sebsauvage Messages postés 32893 Date d'inscription mercredi 29 août 2001 Statut Modérateur Dernière intervention 21 octobre 2019 15 655
25 juin 2003 à 11:19

>grabscreen
jamais essayé.

>C'est a toi Wiki?
Non c'est à William Dodé. J'ai juste contribué au remplissage du wiki.
Il intervient de temps en temps sur fr.comp.lang.python.
Très sympa.

>Sinon, pourquoi tu fais pas un site "Python Sauvage"?
oui oui... elle est bonne... mais j'ai l'habitude...

J'essaie de ne pas trop multiplier mes pages sur Python: le but c'est pas de faire un doublon avec les principaux wiki Python existants (français et autres). Ils font déjà un excellent boulot (présenter Python, guider, donner des exemples, des outils...).
Je met juste mes petites astuces, bouts de code, petits programmes et conseils à moi :)

L'URL que je garde toujours sous le coude: http://www.python-eggs.org/links.html
C'est excellent.

Et je vais voir:
- toutes les semaines: http://www.ddj.com/topics/pythonurl/
- tous les jours: http://www.pythonware.com/daily
J'aime bien parceque ça donne des idées sur ce qu'on peut faire de Python, et d'aborder des aspects ou applications du langage auxquelles on aurait pas pensé.

Réponse 14 / 15

teebo Messages postés 33491 Date d'inscription jeudi 14 octobre 2004 Statut Modérateur Dernière intervention 24 février 2011 1 793
25 juin 2003 à 12:10

Je viens de calculer approximativement qu'il faudrait un mois pour mes 10 millions...
Je crois que je vais pas le faire :-D

. .
\_/

Réponse 15 / 15

Fu Xuen Messages postés 3639 Date d'inscription jeudi 24 avril 2003 Statut Contributeur Dernière intervention 11 septembre 2005 305
25 juin 2003 à 21:06

Une ressource intéressante pour les matheux, indexée par langage de programmation avec une première rubrique pour le Python : [http://www.inetarena.com/~pdx4d/ocn/cp4e.html].

-= Fu Xuen =-

[Python]Erathostene, paris ouverts

15 réponses

Discussions similaires

Newsletters