PRINT - Prime Intervals
In this problem you have to print all primes from given interval.
Input
t - the number of test cases, then t lines follows. [t <= 150]
On each line are written two integers L and U separated by a blank. L - lower bound of interval,
U - upper bound of interval. [2 <= L < U <= 2147483647] [U-L <= 1000000].
Output
For each test case output must contain all primes from interval [L; U] in increasing order.
Example
Input:
2 2 10 3 7
Output:
2 3 5 7 3 5 7
hide comments
|
otoya:
2024-01-28 01:39:22
seg sieve check cp algorithms Last edit: 2024-01-28 01:39:45 |
|
magnesium12:
2023-06-08 18:49:25
very tight time limit, TLE with endl but AC with '\n' |
|
tripodsan:
2023-01-07 12:56:44
@deepamgupta, I wrote a solution in js-monkey and the only way to optimise was to output lines at once. i.e. instead of calling print() 1000 times, concatenate the string, and print() only once. this reduced the execution time by about 1 second. |
|
c7h5n3o6_tnt:
2022-05-23 05:24:12
RE:( It's not wise to use array or vector. |
|
guru_shreyansh:
2021-05-04 12:52:18
Solved in JAVA in 0.55 secs. With bufferedReader & Segmented Sieve. |
|
4444:
2021-01-02 12:11:20
Thank You @i_m_chitti |
|
i_0__0_i:
2020-11-09 06:59:40
@Roman Sol
|
|
i_am_chitti:
2020-07-25 15:36:29
Use segmented sieve. Don't use cout and cin.
|
|
ganjaboi:
2020-06-21 07:25:29
sieve of eratosthenes will work here or not
|
|
krishp:
2020-05-24 21:23:38
Unfortunately, I do not believe this is solvable in python. Even with optimized segmented sieve + stdin/stdout, you cannot print out all the answers in time. It takes 1.11 seconds just to print out the primes within the range(2147483647-10**6,2147483647) and with 149 other test cases, it just cannot be achieved in time.
|
| Added by: | Roman Sol |
| Date: | 2005-03-28 |
| Time limit: | 1.223s |
| Source limit: | 15000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | ZCon |
RSS