HolyNumbers | Topcoder Archive

Problem Statement

NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.

In John's country, the main religion is based on holy numbers. The religion claims something silly like "the holy numbers are those that contain only 4s and 7s in their decimal expansion".

John is a heretic. He does believe in holy numbers, but he is convinced that the religion is mistaken in their definition. The holiness of a number simply cannot depend on the base in which it is represented! After a long meditation, John realized that the prime factorization of a number does not depend on the base in which the number is represented. That was the correct way!

Many years later, John's theory was finally ready. A prime p likes the number x if one of the following two conditions is satisfied:

The prime p does not divide x.
The prime p does divide x, p is less than or equal to maximalPrime, and the highest power of p that divides x is odd. (In other words, there is a positive odd integer k such that p^k divides x, and p^k+1 does not divide x.)

The number x is considered holy if all primes like it.

You are given a long upTo and the int maximalPrime. Return the count of holy numbers between 1 and upTo, inclusive.

Definition

Class:: HolyNumbers
Method:: count
Parameters:: long, int
Returns:: long
Method signature:: long count(long upTo, int maximalPrime)
(be sure your method is public)

Notes

A prime number is a positive integer with exactly 2 positive integer divisors. The first few primes are 2, 3, 5, 7, 11, ...

Constraints

upTo is between 1 and 1010, inclusive.
maximalPrime is between 1 and 106, inclusive.

Examples

```
10
```
```
100
```
```
Returns: 8
```
1, 2, 3, 5, 6, 7, 8 and 10 are holy numbers.
```
10
```
```
3
```
```
Returns: 5
```
5, 7 and 10 are no longer holy.
```
123
```
```
12
```
```
Returns: 32
```
```
123
```
```
456
```
```
Returns: 88
```
```
123456789
```
```
12345
```
```
Returns: 25994500
```

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.