Code Optimization

[vidit_X]

I need to write a program, which prints out all the prime numbers between two numbers. The first input specifies the number of test cases, followed by the limits. Here is an example..

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

I wrote the following code, but it exceeds the time limit of 6seconds. How can I optimize it to perform faster?

#include<iostream>
#include<cmath>
using namespace std;

bool prime(long);

long primegen(long, long);

int main()
{
 int n;
 long i,j;
 cin>>n;;
 while(n--!=0)
 {
  cin>>i>>j;
  if((j-i) <= 100000)
	  primegen(i,j);
  cout<<"\n";
 }
 return 0;
}

long primegen(long i, long j)
{
 long min=i, max= j;
 
 while(min<=max)
 {
  if(prime(min))
	printf("%ld \n", min);
  if(min==1 || min % 2 == 0)
	  min++;
  else 
	  min=min+2;
 }
 return 0;
}

bool prime(long num)
{
 double j= (double)num;
 if(num == 1)
	 return false;
 if(num == 2)
	 return true;
 if(num % 2 == 0)
     return false;
 for(int i=3; i<= sqrt(j); i=i+2)
	if(num % i == 0)
		return false;
 return true;
}

[Rashakil Fol]

Are you compiling with optimizations on?

Maybe you shouldn't evaluate sqrt(j) every time through the for loop. That sounds like something an optimizer might catch, but even then you're converting i from int to double every round of the loop.

You could use a better prime testing algorithm. Miller-Rabin would do fine. See http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

[vidit_X]

Thanks Rashakil, a better algorithm is what I need.

The program is being evaluated by an online judge(automated) with a fix number of test cases. I think it should have optimizations on.

A good compiler with optimizations will automatically take the invariants out of loop, am I right?

[alwaysLearning0]

is there any upper limit of i/j and any memory limit?

[alwaysLearning0]

if the upper limit of your two number is 2 ^ 32 which is 4294967296 and sqrt of this 65536.

so 65536 is 5 digit number, for a 100,000 there are only 9592 prime numbers according to this site http://primes.utm.edu/howmany.shtml

so generate these 9592 prime numbers first and save this.
and what ever range you get, you just need to find if your range can be divided by these 9592 numbers.

[vidit_X]

if the upper limit of your two number is 2 ^ 32 which is 4294967296 and sqrt of this 65536.

so 65536 is 5 digit number, for a 100,000 there are only 9592 prime numbers according to this site http://primes.utm.edu/howmany.shtml

so generate these 9592 prime numbers first and save this.
and what ever range you get, you just need to find if your range can be divided by these 9592 numbers.

Yes, there is an upper limit on both i and j.

Calculating and storing all the 9952 prime numbers, and then using them would surely be faster but would that be considered a good solution?

[alwaysLearning0]

if it can solve your problem in 6 seconds then of course its a good solution, isn't it?
If it cant then its not a good solution. So you can give it a try.

[alwaysLearning0]

I am not sure why people downvote others when someone tries to help.
Anyway.. here is a solution for your problem.

http://www.rsok.com/~jrm/printprimes.html using this algorithm http://en.wikipedia.org/wiki/Generating_primes#Prime_sieves

[vidit_X]

Thanks alwaysLearning0, I'll check them out.

[Rashakil Fol]

I am not sure why people downvote others when someone tries to help.

My mouse slipped and I didn't realize there is now an undo feature.