Page 1 of 1

Colin and Ryan

Posted: Sun Jul 31, 2005 7:01 am
by temper_3243
My idea is for input n,k is

factorize n-k and output all factors of n-k > 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.

Posted: Sun Jul 31, 2005 7:33 am
by Cho
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?

Posted: Sun Jul 31, 2005 7:33 am
by sharpobject
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(n-k). For each one that was a factor, we added i and (n-k)/i and to a set, then output all members of the set >(n-k).

Posted: Sun Jul 31, 2005 7:11 pm
by abishek
amazing that worked, although even my overall complexity is O(sqrt(n-k)) (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.