[Python]Erathostene, paris ouverts
teebo
Messages postés
33491
Date d'inscription
Statut
Modérateur
Dernière intervention
-
Eaulive Messages postés 27064 Date d'inscription Statut Modérateur Dernière intervention -
Eaulive Messages postés 27064 Date d'inscription Statut Modérateur Dernière intervention -
Salut tout le monde, juste pour vous faire part d'une petite experience, un crible d'eratosthene lance en Python (basique, en n²) sur les 10 000 000 premiers entiers
<rappel>Ce crible permet de trouver les nombres premiers en eliminant tous les mutliples des nombres rencontres</rappel>
Alors 2 paris :
1-Sachant qu'il tourne deja depuis 66h, combien de temps mettra-t-il
2-Aura-t-il le temps de se terminer avant que ma patience ne craque (ca ralenti pas mal la becan ce truc :o) )
. .
\_/
<rappel>Ce crible permet de trouver les nombres premiers en eliminant tous les mutliples des nombres rencontres</rappel>
Alors 2 paris :
1-Sachant qu'il tourne deja depuis 66h, combien de temps mettra-t-il
2-Aura-t-il le temps de se terminer avant que ma patience ne craque (ca ralenti pas mal la becan ce truc :o) )
. .
\_/
A voir également:
- [Python]Erathostene, paris ouverts
- Citizen code python avis - Accueil - Outils
- Deco in paris avis ✓ - Forum Consommation & Internet
- Déco in paris site fiable ???? - Forum Consommation & Internet
- Paris multiple 2/5 explication ✓ - Forum Loisirs / Divertissements
- Steam purchase paris 8 - Forum Jeux vidéo
15 réponses
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 :-)
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 :-)
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 :-)
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 :-)
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 ;-)
. .
\_/
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 ;-)
. .
\_/
gain de temps importants
précédemment trouvés
Désolé :) normalement, je me relis ...
@++
Poster, poster encore et toujours :-)
précédemment trouvés
Désolé :) normalement, je me relis ...
@++
Poster, poster encore et toujours :-)
Ya un type natif pour les gds entiers ?
@++
Poster, poster encore et toujours :-)
@++
Poster, poster encore et toujours :-)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Ca s'adapte :o)
J'ai eu le resultat vrai de 100000! (plusieurs page l'entier :-D)
. .
\_/
J'ai eu le resultat vrai de 100000! (plusieurs page l'entier :-D)
. .
\_/
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 :-)
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 :-)
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:
au début du programme.
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.
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. ;-)
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. ;-)
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)
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)
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 :-)
@++
Poster, poster encore et toujours :-)
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 =-
-= Fu Xuen =-
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)
. .
\_/
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)
. .
\_/
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)
. .
\_/
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)
. .
\_/
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)
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)
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 ==================>
. .
\_/
C'est a toi Wiki?
Sinon, pourquoi tu fais pas un site "Python Sauvage"? Desole, la porte est par la ==================>
. .
\_/
>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é.
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é.
Je viens de calculer approximativement qu'il faudrait un mois pour mes 10 millions...
Je crois que je vais pas le faire :-D
. .
\_/
Je crois que je vais pas le faire :-D
. .
\_/
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 =-
-= Fu Xuen =-
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).
. .
\_/
Ca serait aps plutot n/log(n)=20 000? Voire n/ln(n)=8686 ou n/2log(n)=10 000?
. .
\_/
=> 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 :-)
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
. .
\_/
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 :-)