Discussion :

[miguelod]

Bonjour,
Je ne sais pas si c'est le bon endroit pour publié cela.
J'ai un calcule que je dois effectuer: je dois additionner tous les nombre premiers jusqu'à 2 millions. Donc, j'ai fait une fonction récursive (voir la pièce jointe). Cependant, après 995 récursion j'obtient une erreur "limite de récursion atteinte". Alors, j'ai arrangé une boucle for pour que je puisse me rendre à 2 millions en traitant tous les nombres. Cependant, mon temps d'exécution est énormément long... Cela fait 4h que j'attend et je suis rendu seulement à 1,5million.
Est-ce que quelqu'un saurait comment modifier mon code pour diminué mon temps d'exécution? Ou bien existe-t-il un module qui aiderait à alléger mon code(ex: math?)?
merci beaucoup.

[danielhagnoul]

Code :

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

1
2
3
somme = sum([x for x in range(1, 2000001)])
 
print(somme)

[VinsS]

Code :

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

1
2
3
somme = sum([x for x in range(1, 2000001)])
 
print(somme)

Salut,

Je trouve ta conception des nombres premiers vraiment très permissive, un peu de rigueur, voyons.

[wiztricks]

Salut,

Cela fait 4h que j'attend et je suis rendu seulement à 1,5million.
Est-ce que quelqu'un saurait comment modifier mon code pour diminué mon temps d'exécution? Ou bien existe-t-il un module qui aiderait à alléger mon code(ex: math?)?

Calculer les nombres premiers avec une fonction récursive n'est pas une bonne idée.
Côté algo. un peu de recherche sur Internet vous indiquerait comment optimiser çà.

Sinon, vous pouvez attendre que Tyrtamos passe dans le coin, il adore les nombres premiers et aime bien raconter ce qu'il a fait sur le sujet (mais comme il a déjà raconté çà maintes fois, en cherchant sur Internet vous trouveriez aussi).

- W

[VinsS]

En ces temps de grande entraide voici une proposition à moins de huit secondes:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
from math import sqrt
import time
 
primes = [3, 5, 7, 11]
num = 13
start = time.time()
while num < 2000000:
    max_ = sqrt(num)
    for p in primes:
        if p <= max_:
            if not num % p:
                break
 
        else:
            primes.append(num)
            break
 
    num += 2
 
primes.insert(0, 2)
end = time.time() - start
print("%s nombres premiers at %s" % (len(primes), end))  # --> 148933 nombres premiers at 7.520849704742432

[flapili]

En ces temps de grande entraide voici une proposition à moins de huit secondes:

Joli, chez moi 4s avec votre code ! pour ma part ~15s (bon après moi je respecte l'énoncé )

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math
import time
 
start = time.time()
 
sum_of_primes = 0
 
 
for n in range(1, 2_000_000, 2):
	sqrt_of_n = math.ceil(math.sqrt(n))
	if any(n%i==0 for i in range(2, sqrt_of_n)):
		sum_of_primes += n
 
time_elapsed = time.time() - start
 
print(f"{time_elapsed=}s")
print(f"{sum_of_primes=}")

time_elapsed=15.359041452407837s
sum_of_primes=856957967889

Je m'attendais pas à un facteur 4 quand même

par contre comme on ne sais pas quel est le résultat attendu difficile de savoir si l'on est dans le juste

[VinsS]

flapili, tu peux grandement améliorer ça.

Ceci if any(n%i==0 for i in range(2, sqrt_of_n)): fait que tu vérifies la divisibilité de n par 3 puis 4 puis 5 puis 6 etc...
Il ne faut vérifier la divisibilité que par les nombres premiers et uniquement eux, donc très peu de nombres en fait, d'où la raison de d'abord constituer la liste.

La somme avec mon code: 142913828922

[danielhagnoul]

Salut,

Je trouve ta conception des nombres premiers vraiment très permissive, un peu de rigueur, voyons.

[...] je dois additionner tous les nombre premiers jusqu'à 2 millions [...]

Oops !

Je suis désolé de cette mauvaise réponse, j'ai mal lu la première fois, où j'ai été trop vite, j'avais retenu "additionne tous les nombres jusqu'à 2 millions" !