Find the number of integers x in range ( 1 , N ) for which x and x + 1 have same number of divisors | PHP 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 ; Function call ; Required answer
< ? php $ N = 100005 ; $ d = array_fill ( 0 , $ N , NULL ) ; $ pre = array_fill ( 0 , $ N , NULL ) ; function Positive_Divisors ( ) { global $ N , $ d , $ pre ; for ( $ i = 1 ; $ i < $ N ; $ i ++ ) { for ( $ j = 1 ; $ j * $ j <= $ i ; $ j ++ ) { if ( $ i % $ j == 0 ) { if ( $ j * $ j == $ i ) $ d [ $ i ] ++ ; else $ d [ $ i ] += 2 ; } } } $ ans = 0 ; for ( $ i = 2 ; $ i < $ N ; $ i ++ ) { if ( $ d [ $ i ] == $ d [ $ i - 1 ] ) $ ans ++ ; $ pre [ $ i ] = $ ans ; } } Positive_Divisors ( ) ; $ n = 15 ; echo $ pre [ $ n ] ; return 0 ; ? >