Optimized Summation of all prime numbers under N

user_16125703 0
Viewed 289

There was 10th question in project eular.

The problem is to find the sum of all prime numbers not greater than N.

My soln for the problem is :

int solve(int n){

    bool check[n+1];
    for(int i=0;i<=n;i++){
        check[i]=true;
    }

    for(int i=2;i*i<=n;i++){
        if(check[i]){
            for(int j=i*i;j<=n;j+=i){
                check[j]=false;
            }
        }
    }

    int sum=0;
    for(int i=2;i<=n;i++){
        if(check[i]){
            sum+=i;
        }
    }
    return sum;
}

Still the problem was not optimized enough as i was getting ' termination due to timeout ' message.

How can i optimize this code better.

The constraints are :

1<= T <= 10^4 ( T is no. of test cases )

1<= N <= 10^6

You can try it yourself here

sieve-of-eratosthenes primes algorithm c++
2 Answers

You have T up to 10^4 (number of tests), and for each of them you run your solve() from start.

Just run solve() one time for maximal possible n and save results of check and sums array into global variables, to reuse them later. Then on each test case just return sums[n].

Also don't forget that sum of primes less than maximal N (1 million) is equal to 37550402023, which overflows maximal possible int value, so you have to use 64-bit int64_t instead for sums.

Below is your code with minimal fixups needed to make it very fast, according to my suggestions above:

Try it online!

#include <cstdint>
#include <iostream>

enum { max_n = 1000000 };
bool check[max_n+1] = {};
int64_t sums[max_n+1] = {};

void solve() {
    for(int i=0;i<=max_n;i++){
        check[i]=true;
    }

    for(int i=2;i*i<=max_n;i++){
        if(check[i]){
            for(int j=i*i;j<=max_n;j+=i){
                check[j]=false;
            }
        }
    }

    int64_t sum=0;
    for(int i=2;i<=max_n;i++){
        if(check[i]){
            sum+=i;
        }
        sums[i] = sum;
    }
}

int main() {
    solve();

    int ntests = 0;
    std::cin >> ntests;
    for (int i = 0; i < ntests; ++i) {
        int n = 0;
        std::cin >> n;
        std::cout << sums[n] << std::endl;
    }    
}

Input:

6
10
100
1000
10000
100000
1000000

Output:

17
1060
76127
5736396
454396537
37550402023
user_9415310 
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>
#include <bitset>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    std::vector<int> qn;
    qn.reserve(t);
    int i, tmp, lim = 0;
    for (i = 0; i != t; ++i) {
        std::cin >> tmp;
        qn.emplace_back(tmp);
        lim = std::max(lim, tmp);
    }
    auto primes = std::make_unique<std::bitset<1000000 + 1>>();
    primes->set();
    primes->set(0, false);
    primes->set(1, false);
    int j;
    for (i = 2; i * i <= lim; ++i) {
        if (primes->test(i)) {
            for (j = i * i; j <= lim; j += i) {
                primes->set(j, false);
            }
        }
    }
    std::vector<long long> ans(lim + 1);
    for (i = 2; i <= lim; ++i) {
        ans[i] = ans[i - 1];
        if (primes->test(i)) {
            ans[i] += i;
        }
    }
    for (auto const& q : qn) {
        std::cout << ans[q] << '\n';
    }
    return 0;
}

Read t. Define qn which is the vector that you are going to store your questions in. Use reserve to allocate memory for t element and thus avoid preallocation. Read your questions (tmp), store them in qn and find out which is the greatest of them all (lim). Allocate bitset on the heap via the unique_ptr primes. Run the sieve of Eratosthenes algorithm on primes up to lim. Define the vector ans which is the vector that you are going to store the answers of your questions in. Run the prefix sums algorithm on it that is If the number i is not prime move the sum accumulated so far (ans[i] = ans[i - 1];) otherwise add i to the newly generated sum. Loop through qn and print the answer of each question q.

Admin1
Related