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
skyfullofstars: 2020-07-15 16:26:29

I'm finding num of divisors for each number using prime factorization method and then making a check of O(1).
not using a sieve.
still getting TLE in cpp.
any improvements which I can do?

[NG]: Try using a sieve. Also your factorization method is poor, take on FACTCG2 for practice. Don't post code / source links here, use the forum for questions or hints.

Last edit: 2020-07-15 19:47:30
Shubham Jadhav: 2020-07-12 20:26:18

Fun problem!
Thanks @Hendra Jaya for the hint

scolar_fuad: 2019-07-21 17:37:22

AC in one hit .... Nice one

seive + prime factorization

shubhamrautela: 2018-10-07 18:29:55

is there anyone from india practicing for ICPC?

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.


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.