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
2017-06-24 20:33:11
easy one...
2017-06-19 16:11:22 kp
Removed from todo list after 2 years 10 days. phew
2017-06-07 13:04:09
A/C in third attempt, funny thing is I had gotten to 1.5 seconds by using a heavily optimized but incorrect implementation. Got it to 0.4 with the correct logic. Hint : Corollary of Prime Sieve.
2017-03-27 00:12:06
AC in one go!!
nice question
use sieve and prime factorization

Last edit: 2017-03-27 00:12:37
2016-12-25 20:47:31
thanks @mohitgupta07
2016-09-16 19:01:27
SPOJ really doesn't like java... the same code give tle in java but runs in c :(
Great problem though.
2016-09-04 18:37:41 Anuj Arora
Phewww...........one mistake cost me multiple SIGFPE .....and 3 hours
2016-05-11 00:11:10
to Solve this ques..try for classical problem NDIV too :P :P u need to then just tweak ur algo to get answer for this one..nd whosoever r confused..
hint:- 6=2*3 but 30=2*3*5
:)
2016-02-27 09:35:17 minhthai
a must do!
2015-05-23 09:39:58 Aditya Kumar
Really enjoyed
Sieve+ d(N) + a little bit of implementation
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.