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.
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.
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