PRIME1 - Prime Generator

See on SPOJ


Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

 

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

 

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

 

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

First Solution- Brute Force

 

Yeah, Brute force works too. Though the given constraints are large enough to fail this method, But if you implement it smartly, it will work.

Just check for every number in the range with the check prime() method and print it.

NOTE: This Solution is not recommended. But due to nonexhaustive test cases, it gets through with Time 0.93 sec. 

The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

#include<iostream> #include<math.h> #include<stdio.h> using namespace std; bool checkprime (long int num) { if (num <=1) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; else { bool prime = true; int divisor = 3; int upperLimit =sqrt(num) +1; while (divisor <= upperLimit) { if (num % divisor == 0) return false; divisor +=2; } return prime; } } int main() {int a,b,i,n,j; scanf("%d",&n); for(i=0;i<n;i++) { scanf(" %d %d",&a,&b); printf("\n"); for(j=a;j<=b;j++) { if(checkprime(j)) printf("%d\n",j); } } return 0; }

 

Second Solution- Segmented Sieve Of Eratosthenes

Learn on Wiki

The primes need to be found using the Sieve Of Eratosthenes. However, that is also not enough. The traditional Sieve of Eratosthenes gives us the list of prime numbers till a number N. Here we need to find the prime numbers between M and N.So we need a modified form of Sieve of Eratosthenes which works on the same basic principle but only finds the primes within a range called Segmented Sieve Of Eratosthenes. Go ahead at this point, check out the Wikipedia article on these subjects.

Logic:
We know that 2 is the first prime no. So, if we start from 2(excluding 2) and increment in 2 steps(that is i=i+2) all numbers we get are divisible by 2 at least. So they cannot be prime.So all those numbers we remove from the list(here removal from the list is done by making segment[]=true for that number). Then the next bigger number that is still on the list will surely be a prime number. In our case, it is 3.  3 is a prime number. We start from 3 and increment in steps of 3, we cut-off 6,9,12, and so on. After 2 and 3, the next largest number in the list that has not been removed is 5. Since 4 has only been cut off as it is a composite of 2. We cut 10,15,20 and so on till N.In this way we remove composite numbers and after a while, the list contains only prime numbers.

Segmented Sieve
Say I need to find the prime numbers between 125 and 140. One way is to find all primes till 140 using traditional sieves and then find how many of them are greater than 125. This will not work within limited time constraints. We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.

The first prime is 2.We divide the starting number x=125 by 2.We round off to smaller integer we get 62. We again multiply by 2 we get 124. What is 124? it is the first smaller number than x that is divisible by the prime 2.We start from 124, increment by 2 in each step, and remove all elements between 125 and 140. That is we remove 126,128,130,132,134,136,138,140.What we did was that we did the first step in a traditional sieve but just offset the starting elements to the closest composite number less than the starting point of the range. Next, we do this with the 2nd smallest prime number 3.125/3=41.41*3=123.We start from 123 go till 140 (inclusive) in steps of 3 and cut the numbers 126,129,132,135,138.Next, we do with 5. But from where do we get the prime numbers 2,3,5 and so on and how long do we need to do that?

We must first use a traditional sieve to make a list of primes up to sqrt(N) where N is the larger of the range. Then we will use this list of primes in the segmented sieve operation. This will leave us with the prime numbers in the desired range. Please re-read the above part a number of times and get this concept clear or revert back in case of any query.

The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast. If you increase the segment size then it may give TLE.

This method Decreases the time taken to 0.01 sec.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

//generate Prime using sieve //segmented sieve //limits the memory used, thus inside cache only hence speed up #include <bits/stdc++.h> #define max1(x,y) (x)>(y)?(x):(y) #define s(n) scanint(n) #define sc(n) scanf(" %c",&n) #define sl(n) scanf("%ld",&n) #define sll(n) scanf("%lld",&n) #define sf(n) scanf("%lf",&n) #define ss(n) scanf("%s",n) #define INF (int)1e9 #define EPS 1e-9 #define bitcount __builtin_popcount #define gcd __gcd #define forall(i,a,b) for(int i=a;i<b;i++) #define all(a) a.begin(), a.end() #define pb push_back #define sz(a) ((int)(a.size())) #define mp make_pair #define checkbit(n,b) ( (n >> b) & 1) #define gc getchar_unlocked #define l long using namespace std ; inline void scanint(int &x) { register int c = gc(); x = 0; int neg = 0; for(;((c<48 || c>57) && c != '-');c = gc()); if(c=='-') {neg=1;c=gc();} for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} if(neg) x=-x; } vector<int > primeArray; bool check[50009]; int keep = 1; void initialise() { check[1 ] = 1; for(int i = 3 ; i <=224 ; i+=2){ if(!check[i]){ for(int j = i*i ; j<= 50000 ; j+=2*i) check[j] = true; } } primeArray.pb(2); keep=1; for(int i = 3 ; i<= 50000 ; i++) if(check[i] == false && (i&1)) primeArray.pb(i) , keep++; } bool segment[1000009]; int main() { int t; s(t); initialise(); while(t--) { int a , b; s(a),s(b); if(b <= 50000){ if(a<=2) printf("2\n"); for(int i = a ; i<= b ; i++){ if(check[i] == false && (i&1)) printf("%d\n", i); } continue; } memset(segment , 0 , sizeof segment); for(int i = 0; primeArray[i]*primeArray[i] <= b ; i++) { int begin = a/primeArray[i]; begin *= primeArray[i]; for(int j = begin ; j<= b ; j+= primeArray[i]){ if(j < a) continue; segment[j - a] = true; } } for(int i = 0 ; primeArray[i]*primeArray[i] <= b ; i++){ if(primeArray[i]>= a && primeArray[i]<=b) printf("%d\n",primeArray[i]); } for(int i = a==1?1:0 ; i < b-a+1 ; i++) if(segment[i]==0) printf("%d\n", i+a); } return 0; }