×

# 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 2.3k●18●30●69 accept rate: 1%

 4 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 . answered 26 Dec '12, 21:21 12.4k●47●107●171 accept rate: 12%
 1 you can see my solution , its easy to understand http://www.codechef.com/viewsolution/6806867 answered 22 Apr '15, 23:07 63●1●6 accept rate: 0%
 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 answered 16 Apr '17, 17:03 1 accept rate: 0%
 0 for larger values and input your code is giving the error answered 16 Apr '17, 23:46 41●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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