Find the number of integers x in range ( 1 , N ) for which x and x + 1 have same number of divisors | Python3 implementation of the above 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
from math import sqrt ; NEW_LINE N = 100005 NEW_LINE d = [ 0 ] * N NEW_LINE pre = [ 0 ] * N NEW_LINE def Positive_Divisors ( ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( 1 , int ( sqrt ( i ) ) + 1 ) : NEW_LINE INDENT if ( i % j == 0 ) : NEW_LINE INDENT if ( j * j == i ) : NEW_LINE INDENT d [ i ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT d [ i ] += 2 NEW_LINE DEDENT DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT if ( d [ i ] == d [ i - 1 ] ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT pre [ i ] = ans NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT Positive_Divisors ( ) NEW_LINE n = 15 NEW_LINE print ( pre [ n ] ) NEW_LINE DEDENT