Problem Statement |
| | A non-negative integer n is said to be a sum of two perfect powers if there exist two non-negative integers a and b such that am + bk = n for some positive integers m and k, both greater than 1. Given two non-negative integers lowerBound and upperBound, return the number of integers between lowerBound and upperBound, inclusive, that are sums of two perfect powers. |
| |
Definition |
| | | Class: | SumsOfPerfectPowers | | Method: | howMany | | Parameters: | int, int | | Returns: | int | | Method signature: | int howMany(int lowerBound, int upperBound) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | lowerBound will be between 0 and 5000000, inclusive. |
| - | upperBound will be between lowerBound and 5000000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 2 | | 0 and 1 are both sums of two perfect powers since 0 = 0 + 0 and 1 = 12 + 02. |
|
|
| 1) | |
| | | Returns: 1 | | 5 is a sum of two perfect powers since 5 = 22 + 12 while 6 is not. |
|
|
| 2) | |
| | | Returns: 5 | | Only 30 is not a sum of two perfect powers. |
|
|
| 3) | |
| | | Returns: 0 | | There may be no desired integers in the range. |
|
|
| 4) | |
| | |