Discussion :

[sirelion]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[wiztricks]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[tyrtamos]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[sirelion]

Ç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,

[wiztricks]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[tyrtamos]

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.

[sirelion]

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