## PRIME1 - Prime Generator

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
```
Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

### Information

After cluster change, please consider PRINT as a more challenging problem.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>

using namespace std;

bool prime[32000];
void primes(){
memset(prime,true,sizeof(prime));
prime[0]=false;
prime[1]=false;
for(int i=2;i<sqrt(32000);i++){
if(prime[i]){
for(int j=i*i;j<32000;j+=i){
prime[j]=false;
}
}
}
/*for(int i=2;i<(32000);i++){
if(prime[i])cout<<i<<endl;
}*/
}
int main(){
int t;
primes();
scanf("%d",&t);
while(t--){
long m,n;
bool ans[1000001];
memset(ans,true,sizeof(ans));
scanf("%ld%ld",&m,&n);
if(m<2){
ans[0]=false;
}
for(int i=2;i<=sqrt(n);i++){
if(prime[i]){
long start=(m/i)*i;
if(start<m){
start+=i;
}
//cout<<start<<endl;
if(start==i){
start+=i;
}
for(long k=start;k<=n;k+=i)
{
ans[k-m]=false;
}
}
}
for(long i=0;i<=n-m;i++){
if(ans[i])
printf("%ld\n",i+m);
}
printf("\n");
}
return 0;
}``````
Copy The Code &

Input

cmd
2
1 10
3 5

Output

cmd
2
3
5
7
3
5

### #2 Code Example with Java Programming

```Code - Java Programming```

``````import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class prime1
{

public static void main(String[] args) throws IOException {
int i, m, n, j, k, p, s;
int[] primes = new int[4000];
j = 0;
primes[j++] = 2;
boolean prime;
for(i = 3; i <= Math.sqrt(1000000000); i+=2)
{
prime = true;
for(k = 0; k < j && primes[k] <= Math.sqrt(i); k++)
if(i % primes[k] == 0)
{
prime = false;
break;
}
if(prime) primes[j++] = i;
}

boolean[] isPrime = new boolean[100001];
while(T-->0)
{
m = parseInt(st.nextToken());
n = parseInt(st.nextToken());
if(m < 2) m = 2;
Arrays.fill(isPrime, true);
for(i = 0; i < j; i++)
{
p = primes[i];
s = 0;
if(p >= m) s = p<<1;
else s = m + ((p-m%p)%p);
for(k = s; k <= n; k+=p) isPrime[k-m] = false;
}

for(i = m; i <= n; i++)
if(isPrime[i-m]) System.out.println(i);

System.out.println();
}

System.exit(0);
}
}``````
Copy The Code &

Input

cmd
2
1 10
3 5

Output

cmd
2
3
5
7
3
5