EVENSEMIP - Even Semiprime Runs
A semiprime is a product of two primes such as $9 = 3\times3$ or $580519 = 41\times14159$.
The first ten semiprimes are $4$, $6$, $9$, $10$, $14$, $15$, $21$, $22$, $25$, and $26$.
A run of semiprimes is a contiguous subsequence of semiprimes. For example, $15$, $21$, $22$ is a run but $9$, $14$, $15$ is not because it skips over $10$.
An even run of semiprimes is a run that contains only even numbers. The first even run of length $3$ is $454$, $458$, $466$.
Your task is to find the longest even run of semiprimes between $N$ and $M$, inclusive.
Input
The first line contains $T$ ($1 \le T \le 20$), the number of test cases.
Each test case is one line containing the integers $N$ and $M$ ($1 \le N \le M \le 10^{14}$, $M - N \le 10^7$).
The sum of the differences $M - N$ over all test cases is at most $10^7$.
Output
Print two lines per test case. On the first line, print the length of the longest even run of semiprimes. On the second line, print the numbers in the run.
If there are multiple solutions, print the one with the smallest first number.
It is guaranteed that there is at least one even semiprime between $N$ and $M$.
Example
Input: 16 4 4 4 6 4 8 4 14 6 10 58 62 1 100 1 1000 1 10000 1 100000 1 1000000 5000000 10000000 247425787142 247425787222 247425000000 247425787221 466937174866 466937199999 99999999000000 100000000000000 Output: 1 4 2 4 6 2 4 6 2 4 6 1 6 2 58 62 2 4 6 3 454 458 466 3 454 458 466 3 454 458 466 5 111614 111626 111634 111638 111646 5 5161318 5161322 5161334 5161342 5161346 8 247425787142 247425787162 247425787166 247425787174 247425787178 247425787198 247425787214 247425787222 7 247425787142 247425787162 247425787166 247425787174 247425787178 247425787198 247425787214 4 466937176054 466937176058 466937176066 466937176078 4 99999999199498 99999999199502 99999999199522 99999999199558
Note
This problem was inspired by Zak Seidov's post in the SeqFan mailing list.
hide comments
julkas:
2018-08-11 13:16:57
@traxexeuler Good, interesting problem. What's your timing? And what is maximum even/odd semiprime runs up to 10**14? Last edit: 2018-08-11 15:04:53 |
Added by: | traxex |
Date: | 2018-04-23 |
Time limit: | 20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | SeqFan mailing list |