DIV - Divisors

Let N be a positive integer. In theory it is easy to decide if d(N) (the number of positive divisors of N including 1 and N) is prime or not. Your task is just a little bit harder: compute all N in [1,10^6] for which d(N)=p*q where p and q distinct primes.

Input

There is no input for this problem.

Output

To make the problem less io related write out only every 9-th of them, one per line.

Output:
50
99
162
...
999524
999728
999927

Added by:czylabsonasa
Date:2005-05-16
Time limit:0.705s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Folklore.

hide comments
2014-12-31 15:11:22 Swapnil Borse
phew... took time but accepted in first go.. :)
Enjoyed a lot :)
2014-11-14 17:53:06 Francky
Note for archive : this problem was on Pyramid before this day, now on cube. EB don't have hands on those changes.
2014-08-27 12:57:00 Lakshay Singhal
nyc question...A/C in one go...
2014-08-11 20:05:58 Amitayush Thakur
Requires no specific algorithm or high class number theory only about optimizing the time and a perfect implementation.
2014-06-12 07:21:42 Anmol Garg
@Aditya Kumar Akash 32 should alse be there in the output, then the 9th number will be 50.

2013-11-04 19:58:29 Alexandre Henrique Afonso Campos
Interesting. Up to 3rd number my algorithm works fine, but the final 3 I'm getting
999664
999825
999988
2013-08-11 15:53:45 Aditya Kumar Akash
Can anyone please explain the output ? How 50 comes first -- getting 12, 18, 20, 28, 44, 45, 48 ,50 ,52 as first 9 elements of entire sequence -- so first in output should be 52.

Last edit: 2013-08-11 15:55:31
2013-07-09 02:36:58 samuel
The largest part of the execution time is "factorsieve",so just adjust algorithm
of this part.
2013-01-24 19:30:43 saket diwakar
Nice problem...:)
2013-01-16 06:35:49 Lai Manh Tuan
In order to pass the time limit, you don't need to know any special number theory.
Good implementation is enough
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.