Count of numbers below N whose sum of prime divisors is K
Given two integers K and N, the task is to find the count of integers from the range [2, N – 1] whose sum of prime divisors is K
Example:
Input: N = 20, K = 7
Output: 2
7 and 10 are the only valid numbers.
sumPFactors(7) = 7
sumPFactors(10) = 2 + 5 = 7
Input: N = 25, K = 5
Output: 5
Approach: Create an array sumPF[] where sumPF[i] stores the sum of prime divisors of i which can be easily calculated using the approach used in this article. Now, initialise a variable count = 0 and run a loop from 2 to N – 1 and for every element i if sumPF[i] = K then increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; #define MAX 1000001 // Function to return the count of numbers // below N whose sum of prime factors is K int countNum( int N, int K) { // To store the sum of prime factors // for all the numbers int sumPF[MAX] = { 0 }; for ( int i = 2; i < N; i++) { // If i is prime if (sumPF[i] == 0) { // Add i to all the numbers // which are divisible by i for ( int j = i; j < N; j += i) { sumPF[j] += i; } } } // To store the count of required numbers int count = 0; for ( int i = 2; i < N; i++) { if (sumPF[i] == K) count++; } // Return the required count return count; } // Driver code int main() { int N = 20, K = 7; cout << countNum(N, K); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { static int MAX = 1000001 ; // Function to return the count of numbers // below N whose sum of prime factors is K static int countNum( int N, int K) { // To store the sum of prime factors // for all the numbers int []sumPF = new int [MAX]; for ( int i = 2 ; i < N; i++) { // If i is prime if (sumPF[i] == 0 ) { // Add i to all the numbers // which are divisible by i for ( int j = i; j < N; j += i) { sumPF[j] += i; } } } // To store the count of required numbers int count = 0 ; for ( int i = 2 ; i < N; i++) { if (sumPF[i] == K) count++; } // Return the required count return count; } // Driver code public static void main(String[] args) { int N = 20 , K = 7 ; System.out.println(countNum(N, K)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach MAX = 1000001 # Function to return the count of numbers # below N whose sum of prime factors is K def countNum(N, K) : # To store the sum of prime factors # for all the numbers sumPF = [ 0 ] * MAX ; for i in range ( 2 , N) : # If i is prime if (sumPF[i] = = 0 ) : # Add i to all the numbers # which are divisible by i for j in range (i, N, i) : sumPF[j] + = i; # To store the count of required numbers count = 0 ; for i in range ( 2 , N) : if (sumPF[i] = = K) : count + = 1 ; # Return the required count return count; # Driver code if __name__ = = "__main__" : N = 20 ; K = 7 ; print (countNum(N, K)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 1000001; // Function to return the count of numbers // below N whose sum of prime factors is K static int countNum( int N, int K) { // To store the sum of prime factors // for all the numbers int []sumPF = new int [MAX]; for ( int i = 2; i < N; i++) { // If i is prime if (sumPF[i] == 0) { // Add i to all the numbers // which are divisible by i for ( int j = i; j < N; j += i) { sumPF[j] += i; } } } // To store the count of required numbers int count = 0; for ( int i = 2; i < N; i++) { if (sumPF[i] == K) count++; } // Return the required count return count; } // Driver code public static void Main(String[] args) { int N = 20, K = 7; Console.WriteLine(countNum(N, K)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach const MAX = 1000001; // Function to return the count of numbers // below N whose sum of prime factors is K function countNum(N, K) { // To store the sum of prime factors // for all the numbers let sumPF = new Array(MAX).fill(0); for (let i = 2; i < N; i++) { // If i is prime if (sumPF[i] == 0) { // Add i to all the numbers // which are divisible by i for (let j = i; j < N; j += i) { sumPF[j] += i; } } } // To store the count of required numbers let count = 0; for (let i = 2; i < N; i++) { if (sumPF[i] == K) count++; } // Return the required count return count; } // Driver code let N = 20, K = 7; document.write(countNum(N, K)); </script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(MAX)
Contact Us