You are not logged in. Please login at www.codechef.com to post your questions!

×

Prime Generator Problem

4
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

asked 26 Dec '12, 20:31

upendra1234's gravatar image

2★upendra1234
2.3k183069
accept rate: 1%


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 .

link

answered 26 Dec '12, 21:21

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

you can see my solution , its easy to understand http://www.codechef.com/viewsolution/6806867

link

answered 22 Apr '15, 23:07

shubham54's gravatar image

4★shubham54
6316
accept rate: 0%

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

link

answered 16 Apr '17, 17:03

akashjain619's gravatar image

2★akashjain619
1
accept rate: 0%

for larger values and input your code is giving the error

link

answered 16 Apr '17, 23:46

divyanshu_shuk's gravatar image

2★divyanshu_shuk
411
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,650
×301
×230
×84
×69
×3

question asked: 26 Dec '12, 20:31

question was seen: 5,404 times

last updated: 16 Apr '17, 23:46