Project Euler #10: Summation of primes
Project Euler #10: Summation of primes
+ 34 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 Article
Create 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.
+ 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.
+ 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])
Sort 190 Discussions, By:
Please Login in order to post a comment