HACKER RANK Project Euler 10 - Summation Of Primes - Solution.'C++'

Project Euler Challenges-10 - Summation Of Primes Solution
Problem Statement
This problem is a programming version of Problem 10 from projecteuler.net
The sum of the primes below 10 is 2+3+5+7=17.
Find the sum of all the primes not greater than given N.
Input Format 
The first line contains an integer T i.e. number of the test cases. 
The next T lines will contains an integer N.
Output Format 
Print the value corresponding to each test case in seperate line.
Constraints 
1T104 
1N106
Sample Input
2
5
10
Sample Output
10
17

Solution:

    #include <iostream>
    #include <vector>
    using namespace std;
    const int N=1000000;
    bool mark[N+1000];
    int main()
    {
     vector<int> primes;
     vector<long long> sum;
     for(int i=2;i<=N/2;++i)
      if(mark[i]==false)
      {
       int b=i+i;
       while(b<=N)
       {
        mark[b]=true;
        b+=i;
       }
      }
     primes.push_back(2);
     sum.push_back(2);
     for(int i=3;i<=N;++i)
      if(mark[i]==false)
      {
       primes.push_back(i);
       sum.push_back( sum[sum.size()-1]+i);
      }
     int t;
     cin>>t;
     primes.push_back(10000000);
     for(int k=1;k<=t;++k)
     {
      int n;
      cin>>n;
      int i;
      for(i=0;primes[i]<=n;++i);
      cout<<sum[i-1]<<endl;
     }
     
    }

Thanks for Visiting, Hope this helps you....

Comments

Popular Posts