Count Perfect Sums

Problem Statement

Count Perfect Sums Problem Description You are given a number N . Your task is to count the perfect sums in the range 1 to N . A number is called a perfect sum if it can be expressed as the sum of a perfect square and a perfect cube, that is, as a^2 + b^3 for some integers a >= 1 and b >= 1 . For example, 9 is a perfect sum, since 9 = 1^2 + 2^3 = 1 + 8 . Function Description Complete the function countPerfectSums in the editor. It has the following parameter: int N : the upper end of the range 1..N It returns an int : how many integers v with 1 <= v <= N are perfect sums. Input Format Read from standard input. N A single line containing the integer N . Output Format Print a single integer: the number of perfect sums in the range 1 to N . Constraints 1 <= N <= 100000 The answer is at most N , so a 32-bit integer is enough. Examples Example 1 Input: 5 Output: 2 Explanation: The two perfect sums are 2 and 5 : 2 = 1^2 + 1^3 and 5 = 2^2 + 1^3 . Example 2 Input: 1 Output: 0