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
rahim_17: 2023-12-12 12:24:16

This problem was too interesting very nice problem.

ashok_shaun: 2019-11-11 17:14:20

don't think abt pattern
do sieve...calculate d(n)
do sieve...check for condtns

yaseenmollik: 2019-10-15 09:48:34

After generating some numbers finally got the pattern. And Finally AC!

bhati_r45: 2019-09-06 14:03:05

its really good problem but what is basic method to tackle these types problem as i have seen somebody else solution his way was unique but it was not clicking me

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

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


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