Sort 181 Discussions, By:
Please Login in order to post a comment
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.
limit = 1000000
suml =  * limit
a = [True] * limit
a = a = False
for i, isprime in enumerate(a):
suml[i] = suml[i-1] + i
for n in range(i*i, limit, i):
a[n] = False
suml[i] = suml[i-1]
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
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.
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
Create two seperate arrays for primes and sum of primes.
Solution in Python 3 :
sieve = [True] * lim
for i in range(3,int(math.sqrt(lim))+1,2):
for j in range(i**2,lim,i):
primes=+[i for i in range(3,lim,2) if sieve[i]]
for i in range(1000001):
for k in range(t):
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.