Count number of integers less than or equal to N which has exactly 9 divisors | PHP implementation of above approach 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
< ? php function countNumbers ( $ n ) { $ c = 0 ; $ limit = sqrt ( $ n ) ; $ prime [ $ limit + 1 ] = array ( 0 ) ; for ( $ i = 1 ; $ i <= $ limit ; $ i ++ ) $ prime [ $ i ] = $ i ; for ( $ i = 2 ; $ i * $ i <= $ limit ; $ i ++ ) { if ( $ prime [ $ i ] == $ i ) { for ( $ j = $ i * $ i ; $ j <= $ limit ; $ j += $ i ) if ( $ prime [ $ j ] == $ j ) $ prime [ $ j ] = $ i ; } } for ( $ i = 2 ; $ i <= $ limit ; $ i ++ ) { $ p = $ prime [ $ i ] ; $ q = $ prime [ $ i / $ prime [ $ i ] ] ; if ( $ p * $ q == $ i && $ q != 1 && $ p != $ q ) { $ c += 1 ; } else if ( $ prime [ $ i ] == $ i ) { if ( pow ( $ i , 8 ) <= $ n ) { $ c += 1 ; } } } return $ c ; } $ n = 1000 ; echo countNumbers ( $ n ) ; ? >