Count of numbers below N whose sum of prime divisors is K | Python3 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
MAX = 1000001 NEW_LINE def countNum ( N , K ) : NEW_LINE INDENT sumPF = [ 0 ] * MAX ; NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT if ( sumPF [ i ] == 0 ) : NEW_LINE INDENT for j in range ( i , N , i ) : NEW_LINE INDENT sumPF [ j ] += i ; NEW_LINE DEDENT DEDENT DEDENT count = 0 ; NEW_LINE for i in range ( 2 , N ) : NEW_LINE INDENT if ( sumPF [ i ] == K ) : NEW_LINE INDENT count += 1 ; NEW_LINE DEDENT DEDENT return count ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 20 ; K = 7 ; NEW_LINE print ( countNum ( N , K ) ) ; NEW_LINE DEDENT