Count number of integers less than or equal to N which has exactly 9 divisors | Function to count numbers having exactly 9 divisors ; Sieve array , initially prime [ i ] = i ; use sieve concept to store the first prime factor of every number ; mark all factors of i ; check for all numbers if they can be expressed in form p * q ; p prime factor ; q prime factor ; if both prime factors are different if p * q <= n and q != ; Check if it can be expressed as p ^ 8 ; Driver Code
def countNumbers ( n ) : NEW_LINE INDENT c = 0 NEW_LINE limit = int ( n ** ( 0.5 ) ) NEW_LINE prime = [ i for i in range ( limit + 1 ) ] NEW_LINE i = 2 NEW_LINE while i * i <= limit : NEW_LINE INDENT if prime [ i ] == i : NEW_LINE INDENT for j in range ( i * i , limit + 1 , i ) : NEW_LINE INDENT if prime [ j ] == j : NEW_LINE INDENT prime [ j ] = i NEW_LINE DEDENT DEDENT DEDENT i += 1 NEW_LINE DEDENT for i in range ( 2 , limit + 1 ) : NEW_LINE INDENT p = prime [ i ] NEW_LINE q = prime [ i // prime [ i ] ] NEW_LINE if p * q == i and q != 1 and p != q : NEW_LINE INDENT c += 1 NEW_LINE DEDENT elif prime [ i ] == i : NEW_LINE INDENT if i ** 8 <= n : NEW_LINE INDENT c += 1 NEW_LINE DEDENT DEDENT DEDENT return c NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 1000 NEW_LINE print ( countNumbers ( n ) ) NEW_LINE DEDENT