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.

hide comments
sarkybastard: 2020-12-05 11:55:58

@the_monster_01 "easy peezy lemon quezzy ||| just did in 5 min"? lies, more like 12 failed attempts over an hour, before finally being accepted 4 days later

Last edit: 2020-12-05 14:04:52
the_monster_01: 2020-12-05 09:02:42

use segmented sieve

the_monster_01: 2020-12-05 09:02:15

easy peezy lemon quezzy ||| just did in 5 min

ranshuman01: 2020-12-02 16:11:30

sieve of eratosthenes not working

t_t: 2020-11-24 08:24:36

Why easy brute force works here? The test cases are not strong enough.

Last edit: 2020-11-24 08:25:45
kumar_07: 2020-11-23 16:08:11

you can find the full cpp solution at this link:
<snip>

[NG]: On this site we write our own code. Also read the footer.

Last edit: 2020-11-23 21:53:34
shreyasz_07: 2020-11-21 05:27:09

Ig its very easy !

maxpayne2502: 2020-11-15 06:20:58

in recent year new way to check a prime number is discovered check that

pika_pika_: 2020-10-29 14:54:11

how to reduce time limit...? please help

pandektis: 2020-10-19 10:02:33

time limit exceeded... all the time.
Even copied a solution found elsewhere, same thing..
What am I missing? (is the browser affecting it? I'm currently in a very old version of chrome)


Added by:Adam Dzedzej
Date:2004-05-01
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6