Project Euler 10 "Sum of Prime Numbers"

The sum of prime numbers less than or equal to 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all prime numbers below 2 million. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2010

I wrote it quickly using mymath I made earlier. (296ms) http://qiita.com/cof/items/45d3823c3d71e7e22920

The algorithm for finding prime numbers is written in mymath, but it is as follows.

  1. Using the Sieve of Eratostenes, make a list of booleans whose prime number is True and non-prime number is False.
  2. Create a list of prime numbers from the list in list comprehension notation.

Then, sum the created list of prime numbers (pri ['list'] below) with sum ().

import mymath
import mytime
import math
def cof():
    target = 2 * (10**6)
    pri = mymath.get_primes(target)
    print sum(pri['list'])

I wondered if the following algorithm was faster, but it was slower. (420ms) It seems that the processing speed differs depending on whether the list is Boolean or a number.

  1. Make a list of numbers. [0,0,2,3,4,5,6,7,8,9,10, ‥](1 is set to 0 in advance.
  2. Loop on prime numbers and set the multiples of the prime numbers contained in the digit string to 0. [0,0,2,3,0,5,0,7,0,0,0, ‥]
  3. Take the sum () of the remaining list.
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)

When I looked at what other people were writing on the correct answer bulletin board, Lucy_Hedgehog's code posted on Fri, 3 May 2013, 19:14 was amazing. When I ran it at home, it took 15ms. I couldn't understand his explanation and code well, but he seemed to use an algorithm different from Eratosthenes (similar to the prime number counting algorithm).

Recommended Posts

Project Euler 10 "Sum of Prime Numbers"
Project Euler # 10 "sum of prime numbers" in Python
Project Euler # 13 "Sum of Large Numbers" in Python
Project Euler # 16 "Sum of Powers" in Python
Discrimination of prime numbers
Project Euler # 6 "Difference in sum of squares" in Python
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 9 Retention of calculation results
Project Euler 25
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
[Project Euler] problem1
Project Euler 28 Inefficient Answer Proposal Create "Spiral Numbers"
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Prime numbers and divisors
Recursively find prime numbers
Prime numbers in Python
This year's prime numbers
Project Euler15 "Lattice Path"
What I learned by solving 30 questions of python Project Euler
Sum of multiple numpy arrays (sum)
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1