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
nadstratosfer: 2018-08-29 18:30:53

The M,N conundrum translated to human:
Find all numbers n such that d(n) > 3 and for every divisor m of n, d(n) % d(m) = 0.

Last edit: 2018-08-29 18:33:15
karthik1997: 2017-12-27 22:28:47

Really Good Question and really good example of modified sieve :)

viratian_070: 2017-06-24 21:34:06

problem statement is not very clear

aashifkhanate: 2017-06-18 06:10:52

Last edit: 2017-06-18 06:11:36
sairaja21: 2017-06-15 15:28:04

does the problem is related with M and N given in the question?

sultania23: 2017-03-09 10:56:26

very nice problem... i spent a day on it..

Last edit: 2017-03-09 10:57:20
tni_mdixit: 2016-10-08 22:00:35

running safely on ideone but tle here @author help
id =17886688

Anuj Arora: 2016-09-04 23:05:38

Similar to DIV ....just pattern observation in the output

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.


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