Count number of integers less than or equal to N which has exactly 9 divisors | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countNumbers ( int n ) { int c = 0 ; int limit = sqrt ( n ) ; int prime [ limit + 1 ] ; for ( int i = 1 ; i <= limit ; i ++ ) prime [ i ] = i ; for ( int i = 2 ; i * i <= limit ; i ++ ) { if ( prime [ i ] == i ) { for ( int j = i * i ; j <= limit ; j += i ) if ( prime [ j ] == j ) prime [ j ] = i ; } } for ( int i = 2 ; i <= limit ; i ++ ) { int p = prime [ i ] ; int 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 ; } int main ( ) { int n = 1000 ; cout << countNumbers ( n ) ; return 0 ; }