Réponse:
bonjour je ne sais pas si ma réponse est la bonne mais essaye de voir j'ai fait tout mon possible pour la trouver
Explications:
Le premier programme est le plus "classique", il calcul tous les nombre premier jusqu’à n, en divisant chaque nombre k allant de 2 à n par tous les nombre i allant de 2 a Racine de k. Si k est divisible par un de ces nombre, il n'est pas premier, sinon, il est premier et je l'ajoute à la liste.
En python, ça donne ça :
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
29
30
31
32
33
34
35
36
import time
from math import sqrt
def isPremier(x):
i = 2
verif = 1
while i <= sqrt(x):
if x % i == 0:
verif = 0
break
else:
i = i + 1
if verif == 0:
return 0
else:
return 1
def nombrePremierJusqua(x):
premier = []
i = 2
if x >= 2:
while i < x:
if isPremier(i) == 1:
premier.append(i)
i = i + 1
return premier
jusqua = input("Calcul des nombres premier jusqu'a : ")
debut = time.clock()
print nombrePremierJusqua(jusqua)[-1]
print "Temps d'execution : ", (time.clock() - debut)*1000
2ème programme
Le deuxième programme est bien mieux pensé. Il possèdent en effet une liste des nombre premier nommer "premier", qui contient au départ, seulement 2.
Pour déterminer tous les nombre premier jusqu’à n, je divise tous les k allant de 3 a n par tous les nombres premiers contenus dans la liste "premier", si le reste des divisions n'est jamais nul, alors le nombre est premier, dans ce cas, je le rajoute à la liste "premier" et je passe au k suivant, sinon, il n'est pas premier.
Voila ce que ça donne en python :
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
import time
from math import sqrt
def nombrePremierJusqua(x):
premier = [2]
i = 3
while i < x:
verif = 1
for p in premier:
if (i % p) == 0:
verif = 0
break
if verif == 1:
premier.append(i)
i = i + 1
return premier
jusqua = input("Calcul des nombres premier jusqu'a : ")
debut = time.clock()
print nombrePremierJusqua(jusqua)[-1]
print "Temps d'execution : ", (time.clock() - debut)*1000
Synthèse et problème
Dans ce cas, il semblerais bien que le programme 2 soit bien plus rapide que le programme 1, étant donné que celui ci a bien moins de division a faire que le programme 1. Toutefois, après test sur de grandes valeur, voila ce que j'obtient :
