SemiPerfectPower | Topcoder Archive

Problem Statement

Magical Girl Iris loves perfect powers. A positive integer n is a perfect power if and only if there are positive integers b > 1 and c > 1 such that b^c = n (where ^ denotes exponentiation). For example, 8 (=2^3) and 243 (=3^5) are perfect powers, while 1 and 54 are not.
One day, Iris discovered that there are very few perfect powers. To avoid being disappointed, she quickly invented the semi-perfect powers: A positive integer n is a semi-perfect power if and only if there are positive integers a >= 1, b > 1, and c > 1 such that a < b and a*(b^c) = n. For example, 243 (=1*3^5) and 54 (=2*3^3) are semi-perfect powers, while 1 and 24 are not.
Note that for some semi-perfect numbers there may be more than one corresponding triple (a,b,c). For example, 432 can be expressed as 2*6^3, but also as 3*12^2.
You are given longs L and R. Calculate and return the number of semi-perfect powers that lie between L and R, inclusive.

Definition

Class:: SemiPerfectPower
Method:: count
Parameters:: long, long
Returns:: long
Method signature:: long count(long L, long R)
(be sure your method is public)

Constraints

L will be between 1 and 8*10^16, inclusive.
R will be between L and 8*10^16, inclusive.

Examples

```
18
```
```
58
```
```
Returns: 9
```
There are 9 semi-perfect powers between 18 and 58, inclusive: 18, 25, 27, 32, 36, 48, 49, 50, and 54.
```
1
```
```
10
```
```
Returns: 3
```
Note that 1 is not considered to be a semi-perfect power.
```
60
```
```
70
```
```
Returns: 1
```
The number 64 is the only semi-perfect power in the given range. Note that there are multiple ways to choose a, b, and c when showing that 64 is a semi-perfect power. Still, each semi-perfect power should only be counted once.

319268319114310

35860463407469139

Returns: 95023825161

```
1
```
```
80000000000000000
```
```
Returns: 169502909978
```

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.