Can you tell me why this generates time limit exceeded in spoj(Prime Number Generator)

Question

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;    

bool prime[1000000500];
void generate(long long end)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;

        for(long long i=0;i<=sqrt(end);i++)
        {
         if(prime[i]==true)
         {
             for(long long y=i*i;y<=end;y+=i)
             {
                 prime[y]=false;
             }
         }
        }
}

int main()
{
    int n;
    long long b,e;
    scanf("%d",&n);
    while(n--)
    {
        cin>>b>>e;
        generate(e);
        for(int i=b;i<e;i++)
        {
            if(prime[i])
                printf("%d\n",i);
        }
    }
    return 0;
}

That's my code for spoj prime generator.
Altought it generates the same output as another accepted code ..

Answer 1

Because it took too long.

Answer 2

You need to make it faster - for test cases such as the range 999900000-1000000000, Eratosthene's sieve algorithm is too slow. There are other alternatives you could try and will yield better results.

PS. Of course I won't tell you which these are. Do your homework. :P

Answer 3

An easy trick to make it faster is to lift out sqrt from the for loop:

double sqrtOfEnd = sqrt(end);
for(long long i=0; i<=sqrtOfEnd; i++)
{
  ...

You don't need to recalculate the square root on every loop.
As pointed out by others this might not be enough and you might have to concider other methods of finding primes.

Answer 4

Since you need to output primes from a number of sequences, may-be keep around the results from previous sievings and only continue to fill in the rest of the table as needed?

Answer 5

You don't need to sieve every number up to the end number. That's just silly. Only operate on the range between beginning and end numbers. (A partial sieve)

I've solved this problem in Python and that was the way I finally managed to do it. I also started by calculating all of the primes up to the square root of the potential maximum, 1000000000. This is only 31623 so it doesn't take long.

From this list use those numbers up to the square root of the current case maximum to sieve the current case.