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.


There is no input for this problem.


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


hide comments
s_a_k_s_h_a_m: 2018-06-11 22:34:41

consider 32,243.... also as numbers whose no of divisor is represented by p*q
32-> (5+1 distinct divisors)->6=3X2

nishant_26: 2018-01-16 15:39:24

east! AC in one go

dunjen_master: 2017-12-30 20:15:04

requires a lot of optimization

viratian_070: 2017-06-24 20:33:11

easy one...

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

Added by:Noszi
Time limit:0.705s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)