Prime Generator Problem

general
, , , , ,
1

I am trying to solve Prime Generator problem and using the sieve of erasthones Algorithm to finding the prime number between two number of large range (m and n (1 <= m <= n <= 1000000000, n-m<=100000) ) and getting RunTime Error related to memory i.e. due to large number the array index fails. Please anyone help me how to use sieve of erasthones Algorithm for this problem.

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
 
using namespace std;

void printPrimeNumbers(unsigned long long int start,unsigned long long int end)
{
    unsigned long long int i,j;
    unsigned long long int *arr = (unsigned long long int *)malloc(sizeof(unsigned long long int)*(end+1));
    for(i = 2;i < end;i++)
    {
                      if(arr[i] == 0)
                      for(j = 2; i*j < end; j++)
                                arr[i*j] = -1;
    }
    
    for(i=start-1; i < end; i++)
    if(arr[i] == 0)
              printf("%llu\n",i);
}

int main()
{
    int t;
    scanf("%d",&t);
    unsigned long long int a,b;
    while(t--)
    {
              scanf("%llu%llu",&a,&b);
              printPrimeNumbers(a,b);
   }
    return 0;
}

link of the solution.link text
Thanks in advance

4 Likes
2

Give the number m , index 0 and the number n , index n-m.
Your algorithm will not terminate in time because you are running a loop from 0 to end ( end = n ) .
n is about 10^9 also .
The way to solve this problem is :

  1. Find all primes till 32000 by Sieve method .
  2. Mark all numbers between m and n as prime . Then use sieve to mark numbers as not prime using primes found in step 1 only .
    Note : A number is not divisible by any prime greater than its square root unless it is prime itself , and hence divisible by itself .
4 Likes
3

you can see my solution , its easy to understand CodeChef: Practical coding for everyone

1 Like
4

Clearly n is <=10^9 so sqrt(n)~32000 so you can improve the complexity with some preprocessing.
Preprocess prime numbers less than 32000.
Now to check any number whether it’s prime or not,one of its divisors must be always less than its square root. Using this property I can say lets check each number whether it’s divisible by a number less than its square root.Below is the link to my solution in C++.

https://www.codechef.com/viewsolution/13338458

5

for larger values and input your code is giving the error