DIV2 - Divisors 2


Let N be a positive integer and d(N) be the number of positive divisors of N including 1 and N. Your task is to compute all N in [1,10^6] for which d(N)>3 and if M divides N then d(M) divides d(N) too.

Input

None.

Output

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

Example

Output:
267
511
753
...
999579
999781
999977

hide comments
Sunny: 2016-08-11 19:15:22

I tried running a loop from square root of a number to its half, counting 2 for each factor and storing the factors and so on as well as storing d(N) for all values starting from 1 to 1000000. I am getting a TLE.

Piyush Kumar: 2016-07-14 14:15:23

For people confused about M, M divides N, so M is a divisor of N.

nami20: 2016-06-08 00:06:49

can anybody explain what is M?

Last edit: 2016-06-08 00:07:14
tanim_kuet: 2015-12-12 21:24:12

What is M?

Sayak Haldar: 2015-01-23 18:04:00

this problem is awesome...:)

Francky: 2014-11-14 17:52:49

Note for archive : this problem was on Pyramid before this day, now on cube. EB don't have hands on those changes.

Bharath Reddy: 2014-09-14 14:17:24

Clever problem. Easy to implement...

যোবায়ের: 2011-09-08 20:24:25

M divides N ==> N % M = 0

~!(*(@*!@^&: 2011-09-08 20:24:25

M divides N <=> M mod N = 0 or N mod M = 0?

>>> please use this terminus: http://mathworld.wolfram.com/Divides.html

Last edit: 2011-09-21 21:29:47

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