Consecutive Prime Sum

help
, ,
1

Can someone tell me how to solve this question for N\le 1000,000,000,000?

2

The sum of first 379324 primes = 1000000541933 > 10^12. And, 379324th prime is 5477083.

So, just generate primes under 5477083, keep on storing the sum in a variable and check if the sum is also a prime. If it is, then increase the answer by 1.

1 Like
3

Is it a O(N^2) approach??

4

I think it will be O(P*Sqrt(N)), where P is the smallest number of primes whose sum exceeds N, and I think that will also be around Sqrt(N), so the complexity should be O(N+PlglgP) (PlglgP for sieve) = O(N)

1 Like
5

I read the question wrong. I was thinking of something else. The complexity is as said by @hemanth_1 and there should be a better way to do this problem.

6

Hey,
You Can Look Into My


[1].(Answered By Kunal Singh)


  [1]: http://www.qa.geeksforgeeks.org/8632/problem-consecutive-prime-sum?show=12026#a12026
7

There’s a simple hack that i used in my approach. Just traverse a simple program for this. From 2 to around 6 x 106. Check every prime and maintain a cumulative sum and check the found sum too and add in an another vector. Well, ofcourse this isnt the solution. This would take around 12-13 seconds to run with a naive approach…

for i in range(2, 6000000):

        if i isPrime:

         addtoSum+= i

         if addedtoSum isPrime:

            addtoVector


There would be around 2203 primes( 5, 17, 41, 197, 281, 7699, 8893...) and last one would be > 12 x 10<sup>9</sup>(range limit). You could copy this list into a manual long long array and on input of N perform a binarySearch and print the index.
2 Likes
8

This problem can be solved by using sieve of primes(http://www.geeksforgeeks.org/sieve-of-eratosthenes/). From these sieve create a vector containing only primes.
{2,3,5,7,11…} then modify this vector as {2,5,10,17,28…} by using a[i]=a[i]+a[i-1] for i>=1. Now from this vector remove 2. Then iterate over all these elements of vector and if they are not prime(use sieve to check) erase them. Now this vector will look like {5,17,41…} and it also sorted vector. Now for suppose q number queries we can simply use binary search and get required answer. EG: upper_bound(a.begin(),a.end(),50)-a.begin() which will give 3 as answer. Time complexity to build sieve O(n) then suppose q queries are there, so TC: O(q* log n + n)

9

Can you provide me the code? And what would be your Time complexity?

10

O(log(2190)) maximum complexity. Here’s the code : http://ideone.com/wNA761

1 Like
11

Can you write down your code in C/C++ ?

12

Where did that “2190” came??

13

@bansal1232 It is very simple to convert just look at the solve() function for main logic. the function below is just used to get that list which has all the prime numbers following the condition.
Incase you’re confused about the Arrays.binarySearch return value then suppose returned index = x, and x >= 0 then the number is found at xth index, else if x < 0 then it must be placed at abs(x + 1)th position in order to maintain the sorted property of the list.

1 Like
14

@vijju123 please look at the function solveforN just below solve() function in my code. Its the size of all prime numbers following property asked in question for range from start = 2 to 555000. This N = 2190. Although its just an approximate value += 10. Depends on range used to generate… Applying binary search for this range it becomes O(log(2190). Hope that helps.

1 Like
15

Yes, i just took a second look. You have mentioned it at the very start “2190 numbers”. Sorry, my bad :stuck_out_tongue:

1 Like