Count integers up to N that are equal to at least 2 nd power of any integer exceeding 1 | C ++ program for the above approach ; Function to count the integers up to N that can be represented as a ^ b , where a & b > 1 ; Initialize a HashSet ; Iterating over the range [ 2 , sqrt ( N ) ] ; Generate all possible power of x ; Multiply x by i ; If the generated number lies in the range [ 1 , N ] then insert it in HashSet ; Print the total count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printNumberOfPairs ( int N ) { unordered_set < int > st ; for ( int i = 2 ; i * i <= N ; i ++ ) { int x = i ; while ( x <= N ) { x *= i ; if ( x <= N ) { st . insert ( x ) ; } } } cout << st . size ( ) ; } int main ( ) { int N = 10000 ; printNumberOfPairs ( N ) ; return 0 ; }