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
function countNumbers ( n ) { let c = 0 ; let limit = parseInt ( Math . sqrt ( n ) , 10 ) ; let prime = new Array ( limit + 1 ) ; prime . fill ( 0 ) ; for ( let i = 1 ; i <= limit ; i ++ ) { prime [ i ] = i ; } for ( let i = 2 ; i * i <= limit ; i ++ ) { if ( prime [ i ] == i ) { for ( let j = i * i ; j <= limit ; j += i ) { if ( prime [ j ] == j ) { prime [ j ] = i ; } } } } for ( let i = 2 ; i <= limit ; i ++ ) { let p = prime [ i ] ; let q = prime [ parseInt ( i / prime [ i ] , 10 ) ] ; if ( p * q == i && q != 1 && p != q ) { c += 1 ; } else if ( prime [ i ] == i ) { if ( Math . pow ( i , 8 ) <= n ) { c += 1 ; } } } return c ; } let n = 1000 ; document . write ( countNumbers ( n ) ) ;