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

hide comments
kp: 2017-06-19 16:11:22

Removed from todo list after 2 years 10 days. phew

iceelement: 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.

ashu121: 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
holmesherlock: 2016-12-25 20:47:31

thanks @mohitgupta07

prasoonbatham: 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.

Anuj Arora: 2016-09-04 18:37:41

Phewww...........one mistake cost me multiple SIGFPE .....and 3 hours

mohitgupta07: 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
:)

minhthai: 2016-02-27 09:35:17

a must do!

Aditya Kumar: 2015-05-23 09:39:58

Really enjoyed
Sieve+ d(N) + a little bit of implementation

Swapnil Borse: 2014-12-31 15:11:22

phew... took time but accepted in first go.. :)
Enjoyed a lot :)


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.