Count of numbers below N whose sum of prime divisors is K | C ++ implementation of the approach ; Function to return the count of numbers below N whose sum of prime factors is K ; To store the sum of prime factors for all the numbers ; If i is prime ; Add i to all the numbers which are divisible by i ; To store the count of required numbers ; Return the required count ; Driver code
#include <iostream> NEW_LINE using namespace std ; #define MAX  1000001 NEW_LINE int countNum ( int N , int K ) { int sumPF [ MAX ] = { 0 } ; for ( int i = 2 ; i < N ; i ++ ) { if ( sumPF [ i ] == 0 ) { for ( int j = i ; j < N ; j += i ) { sumPF [ j ] += i ; } } } int count = 0 ; for ( int i = 2 ; i < N ; i ++ ) { if ( sumPF [ i ] == K ) count ++ ; } return count ; } int main ( ) { int N = 20 , K = 7 ; cout << countNum ( N , K ) ; return 0 ; }