La somme des nombres premiers inférieurs ou égaux à 10 est 2 + 3 + 5 + 7 = 17.
Trouvez la somme de tous les nombres premiers inférieurs à 2 millions. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2010
Je l'ai écrit rapidement en utilisant mymath que j'ai créé plus tôt. (296 ms) http://qiita.com/cof/items/45d3823c3d71e7e22920
L'algorithme de recherche des nombres premiers est écrit dans mymath, mais il se présente comme suit
Ensuite, additionnez la liste créée des nombres premiers (pri ['list'] ci-dessous) avec sum ().
import mymath
import mytime
import math
def cof():
target = 2 * (10**6)
pri = mymath.get_primes(target)
print sum(pri['list'])
Je pensais que l'algorithme suivant était plus rapide, mais il était plus lent. (420ms) Il semble que la vitesse de traitement diffère selon que la liste est bourienne ou numérique.
def cof2():
target = 2 * (10**6)
L = [0,0]+range(2,target+1)
L[4::2] = [0] * (len(L[4::2]))
p=3
p_max = int(math.sqrt(target))
while p<=p_max:
if L[p]:
L[p*2::p] = [0] * (len(L[p*2::p]))
p+=2
L.remove(0)
print sum(L)
Quand j'ai regardé ce que les autres écrivaient sur le babillard des réponses correctes, le code de Lucy_Hedgehog publié le vendredi 3 mai 2013 à 19:14 était incroyable. Quand je l'ai couru à la maison, cela a pris 15ms. Je ne comprenais pas bien son explication et son code, mais il semblait utiliser un algorithme différent (similaire à l'algorithme de comptage des nombres premiers) d'Eratostenes.
Recommended Posts