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

#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 ..

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.

This problem requires a Segmented Sieve implementation. A simple segmented Sieve of Eratosthenes can be easily programmed in C/C++ in about 50-60 lines of code. If you implement a segmented sieve, you need to only allocate memory for the maximum sized segment mentioned in the problem.

There are a couple of other optimizations that can help a bit. I will list the ones I did in my solution:

• Check for multiples of only prime numbers up to the square root of the maximum number.

• A lookup array of all prime numbers till the square root of the maximum possible number i.e sqrt(10^9) can be pre-calculated and added to the source code. SPOJ source code size limit is 50000 bytes for this problem and adding this lookup array still fits within this size limit.

• While crossing out multiples, start from y=i*i, but check only odd multiples of i.

With these optimizations my code in C++ ran in about 0.05s. Even without these optimizations I think a segmented sieve should get accepted. Hope this helps.

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.

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?

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

@nakedfantaic Exactly!

#include <cstdio>
#include <cmath>

unsigned int numbers[3500], len;

inline bool prime(unsigned int x)
{
    unsigned int i, last = sqrt(x);
    for (i = 2; i <= last; i++) {
        if (!(x % i)) {
            return 0;
        }
    }
    return 1;
}

void generate()
{
    for (unsigned int i = 2; i < 32000; i++) {
        if (prime(i)) {
            numbers[len++] = i;
        }
    }
}

inline bool process(unsigned long x)
{
    unsigned int i, last = sqrt(x);
    for (i = 0; i < len && numbers[i] <= last; i++) {
        if (!(x % numbers[i])) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int tests;
    unsigned long begin, end;
    generate();
    scanf("%d", &tests);
    while (tests-- > 0) {
        scanf("%u %u", &begin, &end);
        if (begin == 1) {
            begin++;
        }
        while (begin <= end) {
            if (process(begin)) {
                printf("%u\n", begin);
            }
            begin++;
        }
        printf("\n");
    }
    return 0;
}

http://pastebin.com/G5ZRd5vH

I can help with python 3.4 and my working code for spoj(prime generator) is like this:

import math
primes = [True for i in range(int(math.sqrt(1000000000))+1)]
tes = int(math.sqrt(math.sqrt(1000000000)*2))+1
for i in range(2,tes):
    if primes[i]:
        for z in range(i*i,int(math.sqrt(1000000000))+1,i):
            primes[z] = False
for z in range(int(input().strip())):
    m,n = map(int,input().strip().split())
    if n == 1:
        print('')
        continue
    elif m == 1:
        m += 1
    ans = [True for i in range(n-m+1)]
    for i in range(2,int(math.sqrt(1000000000))+1):
        if primes[i]:
            if i > n:
                break
            num = m//i
            if num*i != m:
                num += 1
            if num < 2:
                num = 2
            while num*i <= n:
                ans[num*i-m] = False
                num += 1
    for i in range(n-m+1):
        if ans[i]:
            print(i+m)
    print('')