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
with .
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 and 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
hide comments
hodobox:
2016-08-20 23:33:12
sum of (Nmax-Nmin) < 10^8, as far as I can tell |
|
Francky:
2014-12-15 00:12:08
@ Blue Mary : What do you recommend for this problem, with the switch to cube ?
|
|
[Rampage] Blue.Mary:
2014-12-13 07:16:21
Source limit 2kB still allows pre-calculated table, for example, my code. |
|
Francky:
2014-12-03 23:03:38
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.
|
|
[Lakshman]:
2014-12-02 18:26:49
This problem was moved to CUBE but no Re-judge has been done.
|
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 |