It's All About Three
Time limit1sMemory limit128 MB
For each input number, decide whether every prime factor ends in the digit 3.
- Level
Medium4 of 10
- Topics
- Number theory, Math, Implementation
- Solved
- No attempts yet
Problem
Consider the sequence of numbers in which every prime factor has 3 as its least (right-most) digit. For example, the first 10 numbers of this sequence are:
3 9 13 23 27 39 43 53 69 73
The numbers 3, 13, 23, 43, 53, and 73 belong to the sequence because they are primes whose least digit is 3. The numbers 9 (3×3), 27 (3×3×3), 39 (3×13), and 69 (23×3) also belong because every one of their prime factors has 3 as its least digit.
Write a program that, given a list of positive integers, decides for each integer whether or not it belongs to this sequence.
Input
The input is a list of one or more positive integers, each given on its own line. Each integer is less than 1,000,000. The last line contains -1, which is not part of the list.
Output
For each number in the input, print on its own line the number itself, followed by a single space, and then "YES" if the number belongs to the sequence described above or "NO" if it does not.