Projet Euler 10 "Somme des nombres premiers"

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

  1. À l'aide du tamis d'élastotence, faites une liste de bourians dont le nombre premier est Vrai et le nombre non primaire est Faux.
  2. Créez une liste de nombres premiers à partir de cette liste en notation d'inclusion de liste.

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.

  1. Faites une liste de nombres. [0,0,2,3,4,5,6,7,8,9,10, ‥](1 est mis à 0 à l'avance.
  2. Faites une boucle pour les nombres premiers et définissez le multiple des nombres premiers contenus dans la chaîne numérique sur 0. [0,0,2,3,0,5,0,7,0,0,0, ‥]
  3. Prenez la somme () de la liste restante.
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

Projet Euler 10 "Somme des nombres premiers"
Projet Euler # 10 "somme des nombres premiers" en Python
Projet Euler # 13 "Somme des grands nombres" en Python
Projet Euler # 16 "Somme des pouvoirs" en Python
Discrimination des nombres premiers
Projet Euler # 6 "Différence de somme des carrés" en Python
Projet Euler 7
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 9 Conservation des résultats des calculs
Projet Euler 25
Projet Euler # 3 "Maximum Prime Factors" en Python
Projet Euler # 7 "1000 1er nombre premier" en Python
Projet Euler # 2 "Even Fibonacci Number" en Python
Projet Euler # 17 "Nombre de caractères" en Python
Projet Euler # 1 "Multiple de 3 et 5" en Python
[Projet Euler] problème1
Projet Euler 28 Proposition de réponse inefficace Créer des "numéros en spirale"
Résoudre avec Ruby et Python AtCoder ABC084 D Somme cumulative des nombres premiers
Nombres premiers et fractions
Trouver des nombres premiers récursivement
Nombre premier en Python
Le nombre premier de cette année
Projet Euler15 "Chemin du treillis"
Ce que j'ai appris en résolvant 30 questions du projet python Euler
Somme de plusieurs tableaux numpy (somme)
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1