My idea is for input n,k is
factorize nk and output all factors of nk > k.
Btw how do you guys generate primes until 45000. Sieve or you put it in an array.
If any elegant methods please do post.
Colin and Ryan
Moderator: Board moderators
Oops... I've posted with the same topic in Volume108. And my solution is every bit the same as yours. WAs.
You got WA? or AC but looking or alternative solution?
You got WA? or AC but looking or alternative solution?
Last edited by Cho on Sun Jul 31, 2005 7:34 am, edited 1 time in total.

 New poster
 Posts: 4
 Joined: Sun Jul 31, 2005 6:37 am
 Contact:
well one could just use a program to write a text array literal containing all primes up to 44711 (<5000 of them, so it's not rediculous) then copy the array literal into your program for submission. Alternately, my team ran a brute force with all numbers (not primes, just numbers) up to sqrt(nk). For each one that was a factor, we added i and (nk)/i and to a set, then output all members of the set >(nk).
amazing that worked, although even my overall complexity is O(sqrt(nk)) (because the first step to generate prime numbers), your algorithm essentially does the same step thru every iteration and for every test case. you could have done the part of enumerating all the primes using a naive primality test by using all numbers till approximately 45000. and then could have used these primes to find all the divisors.
if the number of cases had been large, I guess the two methods would have made a difference between a TLE and an AC.
if the number of cases had been large, I guess the two methods would have made a difference between a TLE and an AC.