Find the number of integers x in range ( 1 , N ) for which x and x + 1 have same number of divisors | C ++ implementation of the approach ; To store number of divisors and Prefix sum of such numbers ; Function to find the number of integers 1 < x < N for which x and x + 1 have the same number of positive divisors ; Count the number of divisors ; Run a loop upto sqrt ( i ) ; If j is divisor of i ; If it is perfect square ; x and x + 1 have same number of positive divisors ; Driver code ; Function call ; Required answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE int d [ N ] , pre [ N ] ; void Positive_Divisors ( ) { for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 1 ; j * j <= i ; j ++ ) { if ( i % j == 0 ) { if ( j * j == i ) d [ i ] ++ ; else d [ i ] += 2 ; } } } int ans = 0 ; for ( int i = 2 ; i < N ; i ++ ) { if ( d [ i ] == d [ i - 1 ] ) ans ++ ; pre [ i ] = ans ; } } int main ( ) { Positive_Divisors ( ) ; int n = 15 ; cout << pre [ n ] << endl ; return 0 ; }