Generating prime numbers between m and n

Question

This is a practice problem on spoj.com http://www.spoj.com/problems/PRIME1/ ..

my submission gives "time limit exceeded"

constraints are : 1 <= m <= n <= 1000000000, n-m<=100000 time limit for maximum 10 test cases : 6 s

I wrote the following code based on the sieve of eratosthenes ,

void sieve(int m,int n)
{
       bool prime[1000005]; 
        bool prime2[1000005];
  int i;
    int k;

   prime[0]=1;
   prime[1]=1;

   int mi=sqrt(n);

   for (int i=2; i<=mi; i++)
      if (prime[i]==0)
         for ( k=i*i; k<=n; k+=i)
            {
                if(k<=mi)
            prime[k]=1;

            if(k>=m)
            {

            prime2[k-m]=1;
            }

            }


    int u=min(n,(int)1000000);
   for(i=0;i<u;i++){

    if(prime2[i]==0 && i+m>=2 && i+m<=n)
    printf("%d\n",i+m);
   }
            printf("\n");


}

here 'm' and'n' are the range of numbers between which we have to generate prime numbers.

The problem i'm facing is when I take input as 100000000 100100000 it takes 1.04 s to run (ideone.com C++ 4.3.2) and for 10000000 10100000 it takes 0.07 s

1) why the huge difference between the times , what is contributing to this ?

2) Is there an even faster way to approach this problem ?

`i` starts at `2` and runs to `sqrt(n)` - surely it's easy to understand why increasing `n` by a factor of 10 makes it a lot slower? — Bernhard Barker, May 22 '14 at 13:43
You should probably fix the bugs in your code first before working on performance. For a start, `prime` and `prime2` are never initialised. Did you see any compiler warnings ? — Paul R, May 22 '14 at 13:43
Don't recompute the sieve every time, compute it once and then just iterate over it for each input. Also the code is kind of a mess, first you declare i, then you shadow it in a for loop, the u check doesn't make much sense, etc. -EDIT- WAIT! Are you seriously iterating from 0 to max every time and checking whether that index is inside the range? — Xarn, May 22 '14 at 13:43
@Xarn Given that the range goes up to `1000000000`, calculating all of it might take too long (to be confirmed). — Bernhard Barker, May 22 '14 at 13:48
@PaulR ..it gives correct answer...initialisation is not needed — guitar_geek, May 22 '14 at 13:49
Do you _really_ indent your code like this? You didn't feel any shame when you posted it here? You didn't think "hmm, I'm posting this in public and asking people to look at it for free, so maybe I should make it look less like Satan's posterior and more like happy C++ code?" — Lightness Races in Orbit, May 22 '14 at 13:51
@user2657257: you have a lot to learn about programming - just because something *appears to work* does not mean that it is bug free. Surely you can see that these arrays are never initialised and therefore you have undefined behaviour ? — Paul R, May 22 '14 at 13:51
@Dukeling Well, Erastothenes sieve has complexity of `O(n log log n)` and you have 6 seconds for the task. Lazy evaluation of it is very, very inefficient so by process of elimination you are left with computing full sieve (and enjoying pretty good cache behaviour of said algorithm) and then just iterating over it. — Xarn, May 22 '14 at 13:54
Now we practically got answers to both questions in the comments. You guys should rewrite it as an answer. — AliciaBytes, May 22 '14 at 13:57
@Xarn .. after correcting the range checking also it still takes same time . — guitar_geek, May 22 '14 at 14:05
@PaulR.. isn't it automatically initialised to 0 ? when I print the value of "prime" array, all elements are 0 . — guitar_geek, May 22 '14 at 14:09
@user2657257 In debug mode, it can be. In release, definitely not. — Xarn, May 22 '14 at 14:16
@user2657257 If you define it as a global variable, it will be zero-initialized. Inside the function (on the stack), not such luck — Niklas B., May 22 '14 at 15:46
@Xarn sieve on 1 billion elements is definitely to slow, the processor is *very* slow (probably 7-10 times slower than your PC). *Maybe* it could work with a highly optimized version of the sieve such as the one needed for http://www.spoj.com/problems/KPRIMES2/, but that's *extremely* hard to get fast enough. O((n-m) sqrt(n)) passes as well as O((n-m) log log n) or similar — Niklas B., May 22 '14 at 16:18

Abhishek Bansal · Accepted Answer · 2014-05-22T14:10:06.590

1) why the huge difference between the times , what is contributing to this ?

The difference in time is coming because the time needed to build the sieve is different for both the ranges. It will be higher for bigger numbers.

2) Is there an even faster way to approach this problem ?

As stated in the comments, you are computing the sieve for every test case. You need to build the sieve only once and only up to sqrt(1000000000) = 100000.

My solution (long ago) was as follows:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iterator>

bool is_prime (const int& n, std::vector<int>& v);

int main() {
  int t;
  std::cin >> t;
  std::vector<int> prime_array;

  // build the sieve
  for (int i=2; i<=100000; i++)
    if ( is_prime( i, prime_array ) ) 
        prime_array.push_back( i );

  while (t--) {
    long long m;
    long long n;

    std::cin >> m;
    std::cin >> n;

    if (m<2) m = 2;

    //check for the prime numbers in the range.
    for (int i=m; i<=n; i++)
      if ( is_prime( i, prime_array ) ) 
        std::cout << i << std::endl;
    std::cout << std::endl;

  }
  return 0;
}


// we need to check for prime factors up to sqrt(n)
bool is_prime (const int& n, std::vector<int>& v) {
  double root = sqrt (n);
  std::vector<int>::iterator it = v.begin();
  while ( it != v.end() && *it <= root ) {
    if (!( n % *it)) return 0;
    it++;
  }
  return 1;
}

modified my code, as you somewhat suggested, got accepted. a little slow, but it'll do for now — guitar_geek, May 22 '14 at 16:59

Generating prime numbers between m and n

1 Answers1

Linked