Euler’s Totient Function

As you might know, Euler’s totient function φ(n) is defined as the number of positive integers a, a ≤ n that are relatively prime to n. Two numbers are relatively prime if their greatest common divisor is

1. If the prime factorization of n = pe1 pe2 . . . pej is known the value of φ(n) can be calculated via the 12j Πj (pi − 1)pei−1 following formula: Now your task is to calculate the positive integers n which fulfill the equation φ(n) = x for a given x. Input The input consists of a number of lines. On each line there is a single positve integer with no leading zeros. There are no spaces in the input. All numbers will be positive integers smaller than 1000000000. Output For each line of input there should be one line of output. If the equation φ(n) = x has a solution, print all its solutions on a single line. The solutions should be printed in ascending order and should be seperated by a space. If there is no solution to the equation, print: ‘No solution.’ Sample Input 1 3 6 Sample Output 12 No solution. 7 9 14 18 i=1 i