SPOJ: PRIME1 – Prime Generator

Problem Link

http://www.spoj.com/problems/PRIME1/

Problem Description

In this problem, We need to print all the prime numbers between two given values m and n.

Concepts Used

This problem is based on prime sieve(Sieve of Eratosthenes).

Code

#include<stdio.h>
void sieve(long long int,long long int,bool[],bool[]);
int main()
{
    long long int m,n;
    int t;

    /*scan number of test cases*/
    scanf("%d",&t);

    while(t--)
    {
        bool arr[100002]={0};
        bool brr[100000]={0};

       /*scan m and n */
       scanf("%lld %lld",&m,&n);

       /*call the function to mark all the prime number between m and n*/
       sieve(m,n,arr,brr);

       /*traverse arr[] and print all the unmarked entries*/
       for(long long int l=m;l<=n;l+=1)
       {
           if((arr[l-m]==0)&&(l!=1))
               printf("%lld\n",l);
       }
       printf("\n");
    }

    return 0;
}
void sieve (long long int m,long long int n,bool arr[],bool brr[])
{
    /*j stores first even number to be marked*/
    long long int j;
    if(m%2==0)
        j=m;
    else
        j=m+1;
    if(j==2)
        j+=2;
    /*mark all the even numbers between a and b*/
    while(j<=n)
    {
        arr[j-m]=1;
        j+=2;
    }
    for(long long int i=3;i*i<=n;i+=2)
    {
        if(brr[i]==0)
        {
         long long int c=m%i;
         long long int d;
         /*d stores first multiple of i*/
         if(c!=0)
         d=m+i-c;
         else
          d=m;
         /*marking starts from i*i or d whichever is maximum*/
         if(d<(i*i))
             d=i*i;
         /*mark all the multiples of i starting from d(between m and n)*/
         for(long long int j=d;j<=n;j+=i)
            arr[j-m]=1;
        }
        /*mark all the multiples of i between 1 and sqrt(n)*/
        for(long long int k=i*i;k*k<=n;k+=i)
            brr[k]=1;
    }
}

Explanation

The aim is to find all the prime numbers between m and n. One simple method is to precompute all the prime numbers using prime sieve .Please read the post about prime sieve before reading this post.

But, m and n can have values up to 10^9 ,so we cannot simply implement this method for the given range and store all the prime numbers upto 10^9(we can have a bool array of size 10^8 max).

However, range of n-m (n minus m) is upto 10^5,so we can compute prime numbers between m and n for every test case using optimised version of sieve described in this post. The method is described as follows:

  1. For each test case,we have two arrays arr[] and brr[], both initialised with 0. arr[] is used to mark the prime numbers between m and n,while brr[] is used to mark the prime numbers upto 10^5.(Since maximum possible value of m and n is 10^9,we need to store prime numbers upto 10^5 only ,for marking all the primes)
  2. In sieve earlier described,we start marking the even numbers starting from 4. However,in this case we start from the first even number after m.
  3. In the sieve method described, j starts from i*i,however in this case ,we either start from i*i or the first multiple of i after m,whichever is maximum.
  4. Once we have marked the primes between m and n in arr[], we simply traverse arr[] and print the primes(which have corresponding entries unmarked in arr[])

This content has been helpful to you?

Thanks for contributing!

Yes No