ETL in Prime Numbers problem

[foxo]

Code is working but it exceeds time limit, i don’t have any idea how to make it faster.

Link to the problem: https://www.spoj.com/problems/PRIME1/

In worst case scenario (i.e. t=10,m=999900000,n=1000000000) it takes less than 2s to run the program so i really don’t know what is the issue.

Here is the code:

#include < iostream >

using namespace std;

int main()
{
int t,m,n;

cin>>t;

for(int i=0; i<t; i++)
{
    cin>>m>>n;
    if(m<2) m=2;

    bool a[n+1];

    for(int j=2; j*j<=n; j++)
        {
            if(a[j]==0)
                {
                for(int k=j*j; k<=n; k=k+j)
                    a[k]=1;
                }
        }

    for(int j=m; j<=n; j++)
    {
        if(a[j]==0)
        {
            cout<<j<<endl;
        }
    }
    cout<<endl;
}

return 0;

}

[simes]

You might not want to resieve for primes for each test case.

2
999900000 1000000000
99990000 100000000

With this example, you’ve already sieved for all the primes you need after the first test case, why repeat it for the second? But, even with this change, it’s likely to still be too slow.

You may need a different algorithm. Try searching this forum for some ideas.

[foxo]

Could you give me a hint what to look for? I’ve looked at forum before but everyone sugested using sieve.

[simes]

This. I’m sure one or two suggest other algorithms. Miller Rabin worked for me.