nombres premiers a detecter

bonjour mes chers amis!
ou "Hello, world!" comme on dit chez les novices.
voila.
je commence a m'exercer a réfléchir en langage python après en avoir appris un peu

J'ai un exercice à faire :
écrire la somme des 1000 premiers nombres premiers.
J'ai essaye et le résultat est faux. Je sens bien plusieurs obstacles:
- que je n'arrive pas a traduire une pensée en langage mathématique (Pour tout x, Il existe, si, quelque soit, alors...) dans les termes du langage de programmation.
- que je n'ai pas de méthode pour simuler ce que fait le programme, arrêter a un point et réfléchir.
- un manque de communication avec des gens qui sont passes par des stades similaires au mien.

Je programme en python 3.4.1 et utilise un logiciel libre qui s'appelle Pycharm pour coder, sur d'autres ordi geany ou des fois quand c'est un ordi pas a moi, pythonanywhere en 2.7)

Apres ce préambule voici mon programme (prière de ne pas se moquer!)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

# Un nombre premier est divisible uniquement par 1 et par # lui-meme. n = 3 somme = 2 total = 1 while total < 1001: for x in range (2, n): if n % x == 0: n = n + 1 else: print (n) somme,n, total = somme + n, n + 1, total +1 print("la somme est %d!"%somme)

---

Salut,

Pourquoi ajouter les nombres premiers inférieurs à 1000 en calculant ces derniers en même temps?

Vous pourriez déjà décomposer la chose en 2 actions:

• construction de la liste des nombres premiers inférieurs à 1000
• somme des entiers de cette liste

Si le point 2 est facile, le premier point peut être encore brumeux.
On imagine bien une liste L et une boucle "for" qui teste les nombres de 1 a 1000 pour les ajouter à L si "premier".
Si le truc vous semble assez dégrossi, il faut pianoter à la console pour voir comment traduire cela en Python.

Code:

---

1 2 3 4 5 6 7 8 9 10 11

>>> L = [] >>> for n in range(2, 50): # pour tester pas besoin d'aller jusqu'à 1000 ... for x in range(2, n): ... if n % x == 0: ... break ... else: ... L.append(n) ... >>> L [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47] >>>

---

Reste à optimiser un peu puis ne pas oublier de faire la somme.

- W

Bonjour,

Ce calcul de nombres premiers est un grand classique, et il est intéressant de noter qu'il y a au moins 4 simplifications à intégrer dans le code:

- il est inutile de tester les nombres pairs: on sait déjà qu'ils ne sont pas premiers, sauf 2.

- il est intéressant de garder les nombres premiers dans une liste, parce que ce sont les seuls diviseurs intéressants pour trouver les nombres premiers suivants

- comme on ne teste que les nombres impairs, on va éviter de tester la division par 2: on sait d'avance que ça ne marchera pas. Mais il ne faudra pas oublier d'ajouter 2 à la fin dans la liste des nombres premiers

- quand on divise n par p, il n'est pas utile de tester un p supérieur à la racine carrée de n: si on n'a pas trouvé de diviseur avant, on n'en trouvera pas après.

Voilà un code tout simple qui fait ça:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

from math import sqrt # on aura besoin de la racine carrée   prems = [3] # liste des nombres premiers initialisée à 3 for i in range(5, 1001, 2): # on teste les nombres impairs à partir de 5 pmax = int(sqrt(i)) # inutile de tester au delà de sqrt(i) for prem in prems: if prem>pmax: # i est premier: on le garde et on passe au i suivant prems.append(i) break if i%prem==0: # i n'est pas 1er: on passe au i suivant break prems = [2] + prems # on ajoute 2 au début de la liste des nb 1ers trouvés print(sum(prems)) # et on calcule la somme

---

Ce qui donne: 76127

Les nombres premiers trouvés sont les suivants:

Code:

---

1 2 3 4 5 6 7 8 9

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97, 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191, 193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283, 293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401, 409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509, 521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631, 641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751, 757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877, 881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]

---

Cette méthode par division n'est pas la plus rapide, mais elle est tout de même assez efficace: Pour une valeur maxi de 1 million, le calcul se fait en 3 secondes environ, et la somme fait 37550402023.

Ça c’est vraiment sympa de m'avoir répondu.
Les simplifications concernant les nombres pairs (j'y avais pense) et la racine carrée (modestement je ne savais pas mais j'avais pense a int((x-1)/2) sont judicieuses mais je me suis demande si c’était la peine et si ça accélérait sensiblement le programme.
Le coup d'additionner des nombres premiers c'est je crois ce qu'on appelle la conjecture de Goldbach (lu dans pour la Science il y a des siècles) mais je n'avais pas réussi a trouver comment m'en servir.
Je vais essayer.
J'avais pense faire les boucles avec la "list compréhension" mais ça ne marche pas.
d’emblée j'ai pensé a une boucle While dans while mais ça ne marche pas.

Surtout ce qui me chiffonne c'est pourquoi dans ma liste il y a tant de nombres non-premiers.
Je voudrais utiliser la boucle "for" pour passer dans l'ordre les nombres inférieurs au candidat a la "primauté" et être sur que ça s’arrête des l'apparition d'un "% y == 0"; je voudrais également que juste après une telle procédure on teste le nombre au dessus de ce candidat. Ça ne marche pas.
Donc je ne sais pas incrémenter et j'ai des trous dans la procédure "for".
Si quelqu’un pouvait me montrer mes erreurs ça satisferait ma curiosité.
En passant, c'est super ce forum en français, je passe beaucoup de temps sur des forums anglophones avec l'aide de google translator mais le plaisir de la francophonie n'y est pas.
Python c'est passionnant. Vous êtes sympa.
J'ai essaye de faire au moins 6 programmes en échouant,

Citation:

---

Envoyé par sirelion

Je voudrais utiliser la boucle "for" pour passer dans l'ordre les nombres inférieurs au candidat a la "primauté" et être sur que ça s’arrête des l'apparition d'un "% y == 0"; je voudrais également que juste après une telle procédure on teste le nombre au dessus de ce candidat. Ça ne marche pas.
Donc je ne sais pas incrémenter et j'ai des trous dans la procédure "for".
Si quelqu’un pouvait me montrer mes erreurs ça satisferait ma curiosité.

---

Il y en a trop!
Reprenez votre code:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

n = 3 somme = 2 total = 1 while total < 1001: for x in range (2, n): if n % x == 0: n = n + 1 else: print (n) somme,n, total = somme + n, n + 1, total +1 print("la somme est %d!"%somme)

---

La première est dans le choix du nom de vos variables total ou somme, n ou total?
A mon sens total ne sert à rien sinon à se faire des noeuds au cerveau:

Code:

---

1 2 3 4 5 6 7 8 9 10

n = 3 somme = 2 while n < 1001: for x in range (2, n): if n % x == 0: n = n + 1 else: print (n) somme,n = somme + n, n + 1 print("la somme est %d!"%somme)

---

Vous voyez que vous êtes embêté avec le while n < 1001 qui impose la gestion de "n = n+1".
C'est pour çà qu'on a inventé "range".
Simplifions encore:

Code:

---

1 2 3 4 5 6 7 8 9

somme = 2 for n in range(3, 1001): for x in range (2, n): if n % x == 0: pass else: print (n) somme = somme + n print("la somme est %d!"%somme)

---

Vous voyez mieux (ou pas) que votre code ne fait rien si n % x == 0 et ajoute n à somme sinon.
Si le "n" qu'on ajoute a "somme" est premier ce sera plutôt par hasard.
Pour savoir qu'on a bien essayé tous les nombres dans (2, n) sans succès, on pourrait ajouter un "flag", genre:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

somme = 2 for n in range(3, 1001): premier = True for x in range (2, n): if n % x == 0: premier = False break if premier: print (n) somme = somme + n print("la somme est %d!"%somme)

---

Mais en Python cela s'écrit avec un for...else...

Code:

---

1 2 3 4 5 6 7 8 9

somme = 2 for n in range(3, 1001): for x in range (2, n): if n % x == 0: break else: print (n) somme = somme + n print("la somme est %d!"%somme)

---

L'intérêt de cet exercice n'est pas de calculer des nombre premiers mais de vous motiver à jouer et à apprendre les instructions de contrôle d'une boucle "break", "continue", "for...else..." à travers un défi "calcul de la somme de..." dont l'algorithme de base est simple.
A vous de prendre le temps de lancer la console Python et de tester le comportement de ces différentes instructions.

- W

Citation:

---

Envoyé par sirelion

Le coup d'additionner des nombres premiers c'est je crois ce qu'on appelle la conjecture de Goldbach (lu dans pour la Science il y a des siècles) mais je n'avais pas réussi a trouver comment m'en servir.

---

La conjecture de Goldbach que je connais dit: tout nombre pair supérieur à 3 peut être décrit comme la somme de 2 nombres premiers. Cette conjecture existe depuis... 1742 (!), mais elle n'a pas encore été démontrée mathématiquement. Voir ici: http://fr.wikipedia.org/wiki/Conjecture_de_Goldbach.

Je me suis un peu amusé avec en Python (calculer plein de valeurs pour voir si ça marche): http://python.jpvweb.com/mesrecettes...cture_goldbach.

Pair!!!!!!!
bien sur
si c'etait demontre la congecture prendrait conge et s'appellerait theoreme.
J'adore ces trucs.
quand j'etais jeune j' avais trouve une formule pour calculer la surface d'un cercle a partir de celle du carre de cote egal au diametre (sans se servir de pi) et je voudrais faire ce calcul bientot quand je saurais parler le python.
Je trifouille encore.
j'ai vu dans le livre Byte of python un usage du while avec le "= False " comme dans l' avant dernier code de wiztricks
Je dois reflechir.

Il y a un truc qui me perturbe:
si pour tout y appartenant aux entiers de 3 a x, x modulo y est different de 0,
ecrire x
incrementer le nombre des x trouves a total + 1
incrementer somme a somme plus x
tester la meme chose avec x + 1

quand total n'est plus <= a 1000, imprimer somme et arreter la machine.
c'est un jeu d'enfant, si j'etais un ordinateur je le ferais car je comprends le signifie de ces phrases.
maintenant mon ordinateur parle le patois, non pas moi, le python.
SI POUR ca se dit pour: comme-ca, mais si comme-ci.
le choix "Si pour" c'est le for ..... else . , le "messie" c'est le for ... pass.
Est-on oblige de faire a l'envers?
bon je reviens bientot
Merci beaucoup et je vais faire comme ca commencer avec 1, 2
et voir comment on fait.
Je m'excuse du niveau

Mes chers maitres et amis.
Çà a l'air ridicule mais cette fois-ci j'ai la somme des 1000 premiers nombres premiers,

j'ai un while et deux for.
Seul problème: çà met des heures...
J'ai essaye de l'expliquer en anglais, ou en ce que je crois être de l'anglais

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

# prime number is divisible by 1 and by itself. # in the initialized sum, we have only 2, the first prime number.   sum_of_prime_numbers = 2 # We initialize the total number of prime number that we have found to 1/ total_found_prime_numbers = 1   while total_found_prime_numbers < 1001: # incrementation of the number of prime numbers total_found_prime_numbers = total_found_prime_numbers + 1 for x in range (3, 1000000): # the simplest test for testing if the number is prime (in future # i will stop d to int ((x/2)) for d in range (2, x): if x % d == 0: break else:   sum_of_prime_numbers = sum_of_prime_numbers + x         total_found_prime_numbers = total_found_prime_numbers + 1   print("Somme: ", sum_of_prime_numbers)

---

Je ne savais pas incrémenter la valeur du total des nombres additionnes. Maintenant j'ai compris que l’incrémentation dans la variable manipulée jusqu’à ce qu'elle atteigne tant, dans la boucle while se fait au début du tour suivant, donc juste après la ligne while. J'ai maintenant compris ce que voulait dire wiztricks en disant que le in range d'en haut ferait office de while.

Je serais quand-meme tres reconnaissant si quelqu’un degnait regarder ce petit bout de script pour me dire s'il est malgre tout faux.

Salut,

Citation:

---

Envoyé par sirelion

Je serais quand-meme tres reconnaissant si quelqu’un degnait regarder ce petit bout de script pour me dire s'il est malgre tout faux.

---

Avant de vous lancer dans des calculs "longs", pourquoi ne pas vérifier que çà sort bien des nombres premiers?
Et réfléchir à comment vous assurez que çà le fait...
note: votre truc est faux. Vous le montrer n'a aucun intérêt. Par contre, apprendre à vérifier que votre code fait ce que vous attendez....

- W

Wirlicks
Votre conseil est tres interessant car je pensais le contraire:
Vous faites part d'une experience. Essayer et verifier fait progresser, decortiquer les erreurs pour les mettre en epingle et les rapporter a un point de lacune non.
J'entends cela comme la description d'un fait.
Je le garde precieusement.
En attendant j'ai vu un petit cours en anglais qui est pas mal.
https://www.youtube.com/watch?v=zw2K...?v=zw2Kf13aNcI

hello,
il y a le crible d' Eratosthène pour calculer les nombres premiers. Si vous voulez voir comment optimiser l'algorithme en python 3 regardez 8O ici

Ami calmant, J.P

Je suidés au lait. Je jure assis que porc-équipe est très sympa.
C'est tres joli ce programme.
Je cherche un forum adapte pour exposer et discuter sur des programmes a un niveau tres decouverte et avec beaucoup d'interactivite.
D'un autre cote je vois que les choses ne sont pas du tout rodees.
Je vais refaire des tutoriels:
http://cscircles.cemc.uwaterloo.ca/ (?)
http://learnpythonthehardway.org/book/ (?)

J'ai vu un site sympa: CheckiO assez attrayant mais que des devinettes ce n'est pas structure.

D'un autre cote je me demande si je ne ferais pas mieux de commencer par apprendre a me servir des consoles en bash pour maitriser l'environnement (python anywhere, heroku, et j'en passe restons polis) dont j'ai besoin pour l'avenir

Autre question: J'ai fait un petit mini tutorial sur Ruby qui ressemble beaucoup moins beau que python mais vraiment plus facile. Devrais-je aller la-bas?
Je cherche le chemin par lequel il soit possible de progresser doucement avec une interaction avec des gens plus ou moins de mon niveau.

Je vole du temps pour apprendre et un minimum. Donc je sais que les grands projets ne sont pas pour moi.
Ami calmant votre

Eh oui j'ai fini par y arriver!
mais ma methode n'est pas celle que je voulais avec que des while imbriquees. j'ai fait une fonction et je m'en suis servi.
Ah je ne suis pas fier car je n'ai pas reussi a faire le beau code esthetique que je voulais.
Mais en plus ce mechant codeval me dit failled ...
voici le code

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import math def estpremier(cnp):   tiroir = [] for i in range (2, int(math.sqrt(cnp) + 1)):   reste = cnp % i   tiroir += [reste] if 0 not in tiroir:   return(True) else:   return(False)     cocotier = [2, 3, 5, 7]   for x in range (9, 100000, 2): if estpremier(x) == True: cocotier += [x] if len(cocotier) == 1000: break print("The list cocotier is: ", cocotier) print ("The length of cocotier is ", len(cocotier)) resultat = sum(cocotier) print ("The sum of the thousend first prime numbers is ", resultat)

---

Merci a wiztricks et a marco 056 et a tous ceux qui m'ont aide. Meme si je n'ai pas reussi avec des while.

Quelqu'un aurait-il une idee pourquoi ca ne plait pas a code eval.
Apres la reponse je marquerai resolu.
Il est utile ce forum. C'est quand meme bien d'avoir des amis virtuels pour apprendre a programmer.

Personnellement ce code marche chez moi ! Ça dit d’où vient l'erreur ?
Après pour les nombre premier il y a une simplification sympa à faire.
Si vous prenez un nombre entier quelconque, alors :
il s'écrit de la forme 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 avec k dans N
Pour tout nombre premier supérieur à trois, celui-ci sera forcément de la forme 6k+1 ou 6k+5 sinon il serait divisible par 2 ou 3.
Du coup au lieu de tester tous les pairs, vous pouvez seulement tester les pairs de cette forme.
Concrètement au lieu dans la boucle de faire à la fin i += 2,
on peut faire :
a = 2
i=0
while i<n:
....
i += a
a = 6-a #Prend les valeurs 2, 4, 2, 4, 2, ....

Et vous réduisez de 75% le nombre de nombres à tester, au lieu de 50% ! Après on peut refaire ça avec 5, 7, ... mais j'ai pas creusé plus loin..
Si j'ai le temps j’essaierai de mettre mon algorithme

Tres intéressant. donc on peut aussi mettre des 5x + 2, quand ce n'est pas un 6 x + 1 comme 27, et des 7x + 2 quand ce n'est pas des multiples de 3 comme 37.
c'est FOR INT eressant de voir comment déployer un système pour gérer la raréfaction des nombres premiers avec leur croissance. Chapeau.

Oui mais attention on préférera utiliser les restes de primorielles, cad de nombre de la forme 2*3*5*7*... produit des premiers facteurs premiers, ça évite le si machin divise truc etc, on ramène le problème au reste modulo cette primorielle ! Après c'est une idée ça marche bien pour deux et trois, si tu veux ajouter 5 mon astuce sera plus délicate à mettre en oeuvre, je me suis pas penché sur la question réellement. Mais dans un crible d’Ératosthène tu dois pouvoir mettre en place un petit système dans le genre qui accélère le truc (c'est une ébauche d'idée mais ça mérite d'être creusé je pense)