@Ujjwal: Here's an algorithm for problem 2: Given a number n, form the prime number factorization of n: n = p1^k1 * p2^k2 * ... * pm^km, where the pi are distinct primes and ^ represents exponentiation. If any ki = 1, terminate the factorization and report that n is not a Trojan number. Then calculate gcd(k1,k2,...,km), e.g., by repeated applications of Euclid's Algorithm. Finally, n is a Trojan number if and only if gcd(k1,k2,...,km) = 1. Dave
On Wednesday, October 24, 2012 3:37:28 AM UTC-5, Ujjwal Arora wrote: > We had to code 2 questions in 1.30 hr on codechef only. the questions are > as follow : > > 1.) Implement Least Recently Used (LRU) algorithm - a well known algorithm > of operating systems. > > 2.) Find if a given number is Trojan Number. A Trojan number is a number > which is strong but not a perfect power (m^k). A Strong number is a number > which has a prime number 'p' its factor and also divisible by p^2 i.e > divisible by a prime and also by its square. > Hence, Trojan number is a strong number , which can't be represented as > m^k. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/p3FnJGZAMD4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.