SPOJ.com - Problem PHONY

PHONY - Phony Primes

You are chief debugger for Poorly Guarded Privacy, Inc. One of the top selling product, ReallySecureAgent©, seems to have a problem with its prime number generator. It produces from time to time bogus primes N.
After a while, you realize that the problem is due to the way primes are recognized.
Every phony prime N you discover can be characterized as follows. It is odd and has distinct prime factors, say with , where the number k of factors is at least 3. Moreover, for all i=1..k, divides N-1. For instance, 561 = 3*11*17 is a phony prime.
Intrigued by this phenomenon, you decide to write a program that enumerates all such N's in a given interval $[N_{min},N_{max}[$ with $1 le N_{min} &amp;amp;amp;lt; N_{max} &amp;amp;amp;lt; 2^31, N_{max}-N_{min} &amp;amp;amp;lt; 10^6$ .
Please note, that the source code limit for this problem is 2000 Bytes to avoid precalculated tables.

Input

Each test case contains one line. On this line are written two integers $N_{min}$ and $N_{max}$ separated by a blank. The end of the input is signalled by a line containing two zeros. The number of test cases is approximately 2000.

Output

For each test case, output the list of phony primes in increasing order, one per line. If there are no phony primes in the interval, then simply output none on a line.

Example

Input:

10 2000
20000 21000
0 0

Output:

561
1105
1729
none

Submit solution!

Added by:	Adrian Kuegel
Date:	2004-07-15
Time limit:	1.200s
Source limit:	2000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	ACM Southwestern European Regional Contest, Paris 2003

hide comments



2016-08-20 23:33:12 sum of (Nmax-Nmin) < 10^8, as far as I can tell
2014-12-15 00:12:08 Francky @ Blue Mary : What do you recommend for this problem, with the switch to cube ? 1) No changes. 2) more strict size code limit. 3) new input file. 4) another problem with higher bounds. 5) ??? -- I think 4) is nice, but 1) 2) and 3) are possible too. == @ all : Any other idea ?
2014-12-13 07:16:21 [Rampage] Blue.Mary Source limit 2kB still allows pre-calculated table, for example, my code.
2014-12-03 23:03:38 Francky Oups, I thought I was writing a brute force, sorry. I only put some magic in one place... no opti... My code need 17s at home to cover all 31bit in about 2000 ranges of 10^6. My conclusion is that test cases are weak. I'll write to admin about that : I think we have to strength the IO files. Thanks for your catch, I had a real pleasure to solve this task by the way. --edit--> One trick more and a 10 years old #1 taken :)). --edit2--> There's maybe a rejudge bug as you stated, admin just inform me, the first look was wrong. So I didn't take #1, it's only virtual... but with zero precomputed values ! Last edit: 2014-12-04 01:01:27
2014-12-02 18:26:49 [Lakshman] This problem was moved to CUBE but no Re-judge has been done. --ans(Francky)--> Why do you say that ? It seems (from admin) rejudge had been done, but it seems time limit didn't change. This will be checked again, and maybe rejudge again with a new time limit. I'll check a brute force that should not pass. ---Lakshman->Because a year ago the last submission of Ajay Somani was 12s and that solution is still 12s , and my brute force code which was taking more than 40s on pyramid passes here in 4.7s and I don't see more AC solution. Same with this http://www.spoj.com/problems/CHKL Last edit: 2014-12-03 05:01:47