Code not fast enough

[ne555]

@Cube777:
If you want to store all the primes less than 1e9 you'll need a size of ~48e6 (which you should over-dimensionate)

But that may be too much. You could instead just store the primes to 100e3, and traverse all the range. The primality test would be cheaper as you at most test against 10e3 numbers.

[Cube777]

@Chervil Thanks I don't know why I didn't get that in the first place.. but thanks for the trouble it works great.

So I now uploaded it again and it still says "Time limit exceeded"... I keep looking for new algorithms. Sorry for all the noob mistakes thanks guys for all the help! Good day to you

[dhayden]

So I decided to register with CodeChef and try this one myself. It was surprisingly difficult to get a version that runs in the required time. It's actually a great example of "solve the right problem." When looking for performance, solve the problem at hand, not a more general one. In this case, the part of the problem that can be exploited is[quote]1 <= m <= n <= 1000000000, n-m<=100000[/quote]. This tells us that you're looking at relatively small ranges of numbers (up to 100,000) in a much larger pool (up to 1,000,000,000).

So a fairly quick algorithm is:

compute all the primes up to sqrt(1,000,000,000) = 31,623,
for odd values in each range of numbers
    for each of the primes found
        if prime divides value then
            value isn't prime
            break
    if value is prime then print it 

[MiiNiPaa]

@dhayden

Yes. You created algorithm correctly. That is what I meant by

as preconditions of challenge suggest, a combination of sieve (to get all needed divisors) and brute force (to check all numbers in range).

You can cheat and just store all primes in single array initialized in your source code.
Then just use a binary search to get numbers you need :)

[Cube777]

Hi guys, I rewrote the code and I now use an optimized version of the Sieve of Eratosthenes. I got the source code of the current fastest solution to the problem on CodeChef , ran some benchmark tests and my code is about 50% faster :D But when I uploaded the code to CodeChef I still get an "SIGABRT" error.. I think it is because the "bIsPrimes" array is too large. I'm just going to use Project Euler in the future. Thanks for all the help you guys I learned a lot.

The new code:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <math.h>

using namespace std;

int main()
{
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    int nTestCases;
    cin >> nTestCases;
    int nMinimums[10];
    int nMaximums[10];
    for (int nIndex=0; nIndex!=nTestCases; nIndex++){
        cin >> nMinimums[nIndex] >> nMaximums[nIndex];
    }
    int nMaxAmount=nMaximums[0];
    for (int nIndex=0; nIndex!=nTestCases; nIndex++){
        if (nMaximums[nIndex]>nMaxAmount){
            nMaxAmount=nMaximums[nIndex];
        }
    }
    nMaxAmount++;
    bool* bIsprimes=new bool[nMaxAmount];
    for (int nIndex=3; nIndex<nMaxAmount; nIndex++){
        if ((nIndex%3==0)&&(nIndex!=3)){
            bIsprimes[nIndex]=false;
            continue;
        }
        if ((nIndex%5==0)&&(nIndex!=5)){
            bIsprimes[nIndex]=false;
            continue;
        }
        if ((nIndex%7==0)&&(nIndex!=7)){
            bIsprimes[nIndex]=false;
            continue;
        }
        if ((nIndex%11==0)&&(nIndex!=11)){
            bIsprimes[nIndex]=false;
            continue;
        }
        bIsprimes[nIndex]=true;
    }
    bIsprimes[1]=false;
    int nCurrentPrime=13;
    nMaxAmount--;
    for (; nCurrentPrime*nCurrentPrime<=nMaxAmount;){
        int nMultiplier=nCurrentPrime;
        for (; nMultiplier*nCurrentPrime<=nMaxAmount;){
            for (; (bIsprimes[nMultiplier]==false)&&((nMultiplier+2)*nCurrentPrime<=nMaxAmount); nMultiplier+=2){}
            bIsprimes[nMultiplier*nCurrentPrime]=false;
            nMultiplier+=2;
        }
        nCurrentPrime+=2;
        for (; (bIsprimes[nCurrentPrime]==false)&&(nCurrentPrime<=nMaxAmount); nCurrentPrime+=2){}
    }
    for (int nIndex=0 ;nIndex!=nTestCases; nIndex++){
        if (nMinimums[nIndex]<=2){
            cout << "2" << endl;
            for (; nMinimums[nIndex]%2==0; nMinimums[nIndex]++){}
        }
        if (nMinimums[nIndex]%2==2){
            nMinimums[nIndex]++;
        }
        for (int nSecondIndex=nMinimums[nIndex]; nSecondIndex<=nMaximums[nIndex]; nSecondIndex+=2){
            if (bIsprimes[nSecondIndex]==true){
                cout << nSecondIndex << endl;
            }
        }
        cout << endl;
    }
}

[MiiNiPaa]

I think it is because the "bIsPrimes" array is too large.

Yes. it is 1000000000 bools or ≈1GB of data.
Idea was to generate all possible divisors you will need to test for by sieve (sqrt(1b)≈32k elements) Then just bruteforce each pair using generated divisors.

This challenge is finding balance between speed and memory usage.