
ZOJ Problem Set  3024
Chief Judge's log, stardate 48642.5. We have decided to make a problem from elementary number theory. The problem looks like finding all prime factors of a positive integer, but it is not. A positive integer whose remainder divided by 7 is either 1 or 6 is called a 7N+{1,6} number. But as it is hard to pronounce, we shall call it a MondaySaturday number. For MondaySaturday numbers a and b, we say a is a MondaySaturday divisor of b if there exists a MondaySaturday number x such that ax = b. It is easy to show that for any MondaySaturday numbers a and b, it holds that a is a MondaySaturday divisor of b if and only if a is a divisor of b in the usual sense. We call a MondaySaturday number a MondaySaturday prime if it is greater than 1 and has no MondaySaturday divisors other than itself and 1. A MondaySaturday number which is a prime in the usual sense is a MondaySaturday prime but the converse does not always hold. For example, 27 is a MondaySaturday prime although it is not a prime in the usual sense. We call a MondaySaturday prime which is a MondaySaturday divisor of a MondaySaturday number a a MondaySaturday prime factor of a. For example, 27 is one of the MondaySaturday prime factors of 216, since 27 is a MondaySaturday prime and 216 = 27 × 8 holds. Any MondaySaturday number greater than 1 can be expressed as a product of one or more MondaySaturday primes. The expression is not always unique even if differences in order are ignored. For example, 216 = 6 × 6 × 6 = 8 × 27 holds. Our contestants should write a program that outputs all MondaySaturday prime factors of each input MondaySaturday number. InputThe input is a sequence of lines each of which contains a single MondaySaturday number. Each MondaySaturday number is greater than 1 and less than 300000 (three hundred thousand). The end of the input is indicated by a line containing a single digit 1. OutputFor each input MondaySaturday number, it should be printed, followed by a colon `:' and the list of its MondaySaturday prime factors on a single line. MondaySaturday prime factors should be listed in ascending order and each should be preceded by a space. All the MondaySaturday prime factors should be printed only once even if they divide the input MondaySaturday number more than once. Sample Input205920 262144 262200 279936 299998 1 Output for the Sample Input205920: 6 8 13 15 20 22 55 99 262144: 8 262200: 6 8 15 20 50 57 69 76 92 190 230 475 575 874 2185 279936: 6 8 27 299998: 299998 Source: Asia 2008, Aizu (Japan), Japan Domestic 