SPOJ.com - Problem DIV

DIV - Divisors

#number-theory

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

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	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
	mohitgupta07: 2016-05-11 00:11:10 to Solve this ques..try for classical problem NDIV too :P :P u need to then just tweak ur algo to get answer for this one..nd whosoever r confused.. hint:- 6=23 but 30=23*5 :)
	minhthai: 2016-02-27 09:35:17 a must do!
	Aditya Kumar: 2015-05-23 09:39:58 Really enjoyed Sieve+ d(N) + a little bit of implementation

Submit solution!

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.