# Project Euler #10: Summation of primes

# Project Euler #10: Summation of primes

+ 33 comments For those that aren't passing test case 6 & 7 it's because your prime checking algorithm isn't efficient enough.

There is a very efficient algorithm called the

**Sieve of Eratosthenes**that is very simple. This alorithm will help you create an array of booleans of size 1000000 that will tell you whether a number is a prime or not. Wikipedia ArticleCreate another array that holds the sum of all of the prime numbers less than the index (use the array that we created above)

Once you have the array of sums, simply read the input number, and print sum[inputNumber]. I did this solution in C++ and all test cases finish in < .02 seconds

Reply if you need any help.

+ 2 comments #!/bin/python3 import sys limit = 1000000 suml = [0] * limit a = [True] * limit a[0] = a[1] = False for i, isprime in enumerate(a): if isprime: suml[i] = suml[i-1] + i for n in range(i*i, limit, i): a[n] = False else: suml[i] = suml[i-1] t = int(input().strip()) for a0 in range(t): n = int(input().strip()) print(suml[n])

This is python implementation of sieve of eratosthenes with a list that keeps sum of all prime numbers till n, at index n. Passes all test cases.

+ 0 comments in this problem if test case 1000000 then if your output is 0 than answer is accepted how is possible...there should be answer....37550402023

+ 0 comments Create two seperate arrays for primes and sum of primes.

**Solution in Python 3 :**import math t=int(input()) def nprime(): lim=1000001 sieve = [True] * lim for i in range(3,int(math.sqrt(lim))+1,2): if sieve[i]: for j in range(i**2,lim,i): sieve[j]=False primes=[2]+[i for i in range(3,lim,2) if sieve[i]] return primes def sumprimes(primes): out=[] sumy=0 j=0 for i in range(1000001): if primes[j]<=i: sumy+=primes[j] if j+1<len(primes): j+=1 out.append(sumy) return out primes=nprime() sums=sumprimes(primes) for k in range(t): n=int(input()) print(sums[n])

+ 5 comments All I did was :

1.took help from Project Euler #7

2.created an extra for loop for finding sum

That's it :)

See, how simple it is.

Sort 181 Discussions, By:

Please Login in order to post a comment