Smith | Topcoder Archive

Problem Statement

In 1982 Albert Wilansky called his brother-in-law Smith. During the call Wilansky noticed that the sum of the digits in the phone number was equal to the sum of the digits in the prime factors of the phone number: 4937775 = 3 * 5 * 5 * 65837 and 4 + 9 + 3 + 7 + 7 + 7 + 5 = 3 + 5 + 5 + (6 + 5 + 8 + 3 + 7). Innocent unsuspecting Mr. Smith got numbers named after him.

Numbers with the property described above are called Smith numbers. As all prime numbers trivially have this property they are excluded. The first Smith numbers are: 4, 22, 27, 58, ....

Your task is, given an integer, return how many Smith numbers are less than this integer.

Definition

Class:: Smith
Method:: count
Parameters:: int
Returns:: int
Method signature:: int count(int num)
(be sure your method is public)

Constraints

num is between 2 and 5000000 inclusive

Examples

```
4
```
```
Returns: 0
```
```
23
```
```
Returns: 2
```
```
100
```
```
Returns: 6
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.