## Thursday, August 11, 2016

### [SPOJ] PRIME1 – Prime Generator

http://www.chenguanghe.com/spoj-prime1-prime-generator/
http://www.spoj.com/problems/PRIME1/
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
```

public void solve(int testNumber, InputReader in, OutputWriter out) {
for (int i = 0; i < t; i++) {
if (m < 2) m = 2;
prime(m,n,out);
out.printLine();
}
}
public void prime(int m, int n,OutputWriter out) {
int range = (int)Math.floor(Math.sqrt(n));
boolean[] prime = new boolean[range];
Arrays.fill(prime, 2, prime.length, true);
for (int i = 2; i< range; i++)
if (prime[i])
for (int j = i * i; j < range; j += i)
prime[j] = false;
int[] primes = new int[range + 1];
int cnt = 0;
for (int i = 0; i < prime.length; i++)
if (prime[i])
primes[cnt++] = i;
boolean[] p = new boolean[n-m+1];
Arrays.fill(p,true);
for (int i = 0; i < cnt; i++) {
if (primes[i] == 0)
break;
int low = m / primes[i] * primes[i];
for (int j = low; j <= n; j+=primes[i]) {
if (j < m)
continue;
p[j-m] = false;
}
}
for (int i = 0; i < cnt; i++) {
if (m<=primes[i]&&primes[i]<=n)
out.printLine(primes[i]);
}
for (int i = 0; i < n-m+1; i++) {
if (p[i] && (i+m)!=1)
out.printLine(i+m);
}
}