2
\$\begingroup\$

I have to create a program in which t sets of m and n will be given by the user. For each set, we have to generate all prime numbers between m and n. This code is successfully executed with the correct output, but I have to reduce the time limit for a large data range.

#include<math.h>
#include<stdio.h>
int isPrime(int k); 
int j;
int isPrime(int k) 
 {
  for(j=2; j<=(int)sqrt(k); j++) 
    {
      if(k%j==0)
      return 0;
    }
  return 1;
}

int main()
{
   int u,i,t,m,n,k;        
   scanf("%d", &t);
   while(t--)
       {       
         scanf("%d %d", &m, &n);

         for(i=m;i<=n;i++)
             {
                  u = isPrime(i);
                  if (u == 1)
                  printf("%d\n", i);
             }
       }
   return 0;
}    
\$\endgroup\$
  • 2
    \$\begingroup\$ First off, indent your program properly. \$\endgroup\$ – Michael Zedeler Jun 6 '13 at 17:19
  • 2
    \$\begingroup\$ @WilliamMorris, when people format their code badly, that's something that should be pointed out in a review, not silently corrected. \$\endgroup\$ – Winston Ewert Jun 6 '13 at 22:03
  • \$\begingroup\$ Dunno if this is a SPOJ question but I myself had hard time with this. First look into Seive of Eratosthenes. Also have a look at my code and question about the same. It is still getting timed out but lets see if we can help each other. \$\endgroup\$ – Harish Ved Jun 7 '13 at 11:31
3
\$\begingroup\$

For this SPOJ problem with (1 <= m <= n <= 1000000000, n-m<=100000) limits you will have to use an offset sieve of Eratosthenes.

Since n <= 10^9, to sieve any range under n it is sufficient to have just the primes below its square root, 31622, pre-calculated. There are only 3401 such primes, the biggest being 31607.

So, A. pre-calculate the 3401 primes below 31622.

Since n-m<=100000, you can B. have one array of 100000 booleans preallocated, and sieve it by those primes, as in sieve of Eratosthenes, for each pair m,n.

As an easy optimization, use that sieve segment to represent just odds, without evens: an entry at position i will represent odd(m) + 2*i where odd(m) is the lowest odd number not below m in value. Sieve this segment by odd primes only. No even number above 2 is ever a prime:

for i = 3, 5 ... √n in primes:
   for j = i^2, i^2+2*i, i^2+4*i ...   inside the segment  m ... n:
      A{j} := false
\$\endgroup\$
1
\$\begingroup\$

The main problem is: the algorithm contains a lot of divisions and a lot of function calls. A division can be very time consuming.

As Harish Ved said, the key is the sieve of Eratosthenes. It is one of the simplest and fastest way do determine if a number is prime. With that method, the problem can be solved by zero division and function call.

You should implement the sieve in the main function. You can find a lot of optimized examples on the internet. When You are done with that, You'll have an array, which contains the result of every IsPrime() method you can call. From that point, you only have to check an element of the array to know of a number is prime.

Here You can find a sample sieve (this can be optimized, but probably this will be able to solve the problem in the given time limit too).

You need a maximum value (MAXVAL), the primes smaller than that will be computed.

char *primes = (char*)malloc(MAXVAL*sizeof(char));
primes[0]=primes[1]=0;
for(i=2;i<MAXVAL;i++)
  primes[i]=1;    //allocating memory and filling with 1

for (i=2;i<MAXVAL;i++)
{
if(primes[i])
for(j=i*2;j<MAXVAL;j+=i)
 primes[j]=0;
} //setting the multiples of prime numbers to 0

This little algorithm will generate an array in wich the values at the primeth indexes will be 1, and other values will be 0. So after this, instead of calling Your IsPrime function with a lot of divisions, the prime check of n will look like

if(primes[n])

You can find a little working demonstration HERE

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.