Count numbers in a given range whose count of prime factors is a Prime Number | C ++ program to implement the above approach ; Function to find the smallest prime factor of all the numbers in range [ 0 , MAX ] ; Stores smallest prime factor of all the numbers in the range [ 0 , MAX ] ; No smallest prime factor of 0 and 1 exists ; Traverse all the numbers in the range [ 1 , MAX ] ; Update spf [ i ] ; Update all the numbers whose smallest prime factor is 2 ; Traverse all the numbers in the range [ 1 , sqrt ( MAX ) ] ; Check if i is a prime number ; Update all the numbers whose smallest prime factor is i ; Check if j is a prime number ; Function to find count of prime factor of num ; Stores count of prime factor of num ; Calculate count of prime factor ; Update count ; Update num ; Function to precalculate the count of numbers in the range [ 0 , i ] whose count of prime factors is a prime number ; Stores the sum of all the numbers in the range [ 0 , i ] count of prime factor is a prime number ; Update sum [ 0 ] ; Traverse all the numbers in the range [ 1 , MAX ] ; Stores count of prime factor of i ; If count of prime factor is a prime number ; Update sum [ i ] ; Update sum [ i ] ; Driver Code ; Stores smallest prime factor of all the numbers in the range [ 0 , MAX ] ; Stores the sum of all the numbers in the range [ 0 , i ] count of prime factor is a prime number ; int N = sizeof ( Q ) / sizeof ( Q [ 0 ] ) ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1001 NEW_LINE vector < int > sieve ( ) { vector < int > spf ( MAX ) ; spf [ 0 ] = spf [ 1 ] = -1 ; for ( int i = 2 ; i < MAX ; i ++ ) { spf [ i ] = i ; } for ( int i = 4 ; i < MAX ; i = i + 2 ) { spf [ i ] = 2 ; } for ( int i = 3 ; i * i < MAX ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAX ; j = j + i ) { if ( spf [ j ] == j ) { spf [ j ] = i ; } } } } return spf ; } int countFactors ( vector < int > & spf , int num ) { int count = 0 ; while ( num > 1 ) { count ++ ; num = num / spf [ num ] ; } return count ; } vector < int > precalculateSum ( vector < int > & spf ) { vector < int > sum ( MAX ) ; sum [ 0 ] = 0 ; for ( int i = 1 ; i < MAX ; i ++ ) { int prime_factor = countFactors ( spf , i ) ; if ( spf [ prime_factor ] == prime_factor ) { sum [ i ] = sum [ i - 1 ] + 1 ; } else { sum [ i ] = sum [ i - 1 ] ; } } return sum ; } int main ( ) { vector < int > spf = sieve ( ) ; vector < int > sum = precalculateSum ( spf ) ; int Q [ ] [ 2 ] = { { 4 , 8 } , { 30 , 32 } } ; for ( int i = 0 ; i < 2 ; i ++ ) { cout << ( sum [ Q [ i ] [ 1 ] ] - sum [ Q [ i ] [ 0 ] - 1 ] ) << " ▁ " ; } return 0 ; }