Given an integer N, and an integer K, the task is to count the number of distinct ways to represent the number N as a sum of K unique primes.
Note: Distinct means, let N = 7 and K = 2, then the only way can be {2,5}, because {5,2} is same as {2,5}. So only 1 way.
Examples:
Input: N = 10, K = 2
Output: 1
Explanation:
The only way is {3, 7} or {7, 3}
Input: N = 100, K = 5
Output: 55
Approach: The problem can be solved using Dynamic Programming and Sieve of Eratosthenes.
- Let dp[i][j][sum] be our 3D DP array, which stores the number of distinct ways to form a sum using j number of primes where the last index of prime selected is i in the prime vector.
- The prime numbers can be efficiently computed using Sieve of Eratosthenes. So, we can get a check of prime in O(1) time.
- Recurrence:
We can either include this current prime to our sum, or we can exclude it.
dp[i][j][sum] = solve(i+1, j+1, sum+prime[i]) + solve(i+1, j, sum)
Below is the implementation of the above approach :
C++
// C++ program to count the Number // of distinct ways to represent // a number as K different primes #include <bits/stdc++.h> using namespace std; // Prime vector vector<int> prime; // Sieve array of prime bool isprime[1000]; // DP array int dp[200][20][1000]; void sieve() { // Initialise all numbers // as prime memset(isprime, true, sizeof(isprime)); // Sieve of Eratosthenes. for (int i = 2; i * i <= 1000; i++) { if (isprime[i]) { for (int j = i * i; j <= 1000; j += i) { isprime[j] = false; } } } // Push all the primes into // prime vector for (int i = 2; i <= 1000; i++) { if (isprime[i]) { prime.push_back(i); } } } // Function to get the number of // distinct ways to get sum // as K different primes int CountWays(int i, int j, int sum, int n, int k) { // If index went out of prime // array size or the sum became // larger than n return 0 if (i > prime.size() || sum > n) { return 0; } // If sum becomes equal to n and // j becomes exactly equal to k. // Return 1, else if j is still // not equal to k, return 0 if (sum == n) { if (j == k) { return 1; } return 0; } // If sum!=n and still j as // exceeded, return 0 if (j == k) return 0; // If that state is already // calculated, return directly // the ans if (dp[i][j][sum]) return dp[i][j][sum]; int inc = 0, exc = 0; // Include the current prime inc = CountWays(i + 1, j + 1, sum + prime[i], n, k); // Exclude the current prime exc = CountWays(i + 1, j, sum, n, k); // Return by memoizing the ans return dp[i][j][sum] = inc + exc; } // Driver code int main() { // Precompute primes by sieve sieve(); int N = 100, K = 5; cout << CountWays(0, 0, 0, N, K); } |
Java
// Java program to count the number// of distinct ways to represent// a number as K different primesimport java.io.*;import java.util.*;class GFG{// Prime vectorstatic ArrayList<Integer> prime = new ArrayList<Integer>();// Sieve array of primestatic boolean[] isprime = new boolean[1000];// DP arraystatic int[][][] dp = new int[200][20][1000];static void sieve(){ // Initialise all numbers // as prime for(int i = 0; i < 1000; i++) isprime[i] = true; // Sieve of Eratosthenes. for(int i = 2; i * i < 1000; i++) { if (isprime[i]) { for(int j = i * i; j < 1000; j += i) { isprime[j] = false; } } } // Push all the primes into // prime vector for(int i = 2; i < 1000; i++) { if (isprime[i]) { prime.add(i); } }}// Function to get the number of// distinct ways to get sum// as K different primesstatic int CountWays(int i, int j, int sum, int n, int k){ // If index went out of prime // array size or the sum became // larger than n return 0 if (i >= prime.size() - 1 || sum > n) { return 0; } // If sum becomes equal to n and // j becomes exactly equal to k. // Return 1, else if j is still // not equal to k, return 0 if (sum == n) { if (j == k) { return 1; } return 0; } // If sum!=n and still j as // exceeded, return 0 if (j == k) return 0; // If that state is already // calculated, return directly // the ans if (dp[i][j][sum] != 0) return dp[i][j][sum]; int inc = 0, exc = 0; // Include the current prime inc = CountWays(i + 1, j + 1, sum + prime.get(i), n, k); // Exclude the current prime exc = CountWays(i + 1, j, sum, n, k); // Return by memoizing the ans return dp[i][j][sum] = inc + exc;}// Driver codepublic static void main(String[] args){ // Precompute primes by sieve sieve(); int N = 100, K = 5; System.out.println(CountWays(0, 0, 0, N, K));}}// This code is contributed by akhilsaini |
Python3
# Python3 program to count the number# of distinct ways to represent# a number as K different primes# Prime listprime = []# Sieve array of primeisprime = [True] * 1000# DP arraydp = [[['0' for col in range(200)] for col in range(20)] for row in range(1000)]def sieve(): # Sieve of Eratosthenes. for i in range(2, 1000): if (isprime[i]): for j in range(i * i, 1000, i): isprime[j] = False # Push all the primes into # prime vector for i in range(2, 1000): if (isprime[i]): prime.append(i)# Function to get the number of# distinct ways to get sum# as K different primesdef CountWays(i, j, sums, n, k): # If index went out of prime # array size or the sum became # larger than n return 0 if (i >= len(prime) or sums > n): return 0 # If sum becomes equal to n and # j becomes exactly equal to k. # Return 1, else if j is still # not equal to k, return 0 if (sums == n): if (j == k): return 1 return 0 # If sum!=n and still j as # exceeded, return 0 if j == k: return 0 # If that state is already # calculated, return directly # the ans if dp[i][j][sums] == 0: return dp[i][j][sums] inc = 0 exc = 0 # Include the current prime inc = CountWays(i + 1, j + 1, sums + prime[i], n, k) # Exclude the current prime exc = CountWays(i + 1, j, sums, n, k) # Return by memoizing the ans dp[i][j][sums] = inc + exc return dp[i][j][sums]# Driver codeif __name__ == "__main__": # Precompute primes by sieve sieve() N = 100 K = 5 print(CountWays(0, 0, 0, N, K))# This code is contributed by akhilsaini |
C#
// C# program to count the number// of distinct ways to represent// a number as K different primesusing System;using System.Collections.Generic;class GFG{// Prime vectorstatic List<int> prime = new List<int>();// Sieve array of primestatic bool[] isprime = new bool[1000];// DP arraystatic int[, , ] dp = new int[200, 20, 1000];static void sieve(){ // Initialise all numbers // as prime for(int i = 0; i < 1000; i++) isprime[i] = true; // Sieve of Eratosthenes. for(int i = 2; i * i < 1000; i++) { if (isprime[i]) { for(int j = i * i; j < 1000; j += i) { isprime[j] = false; } } } // Push all the primes into // prime vector for(int i = 2; i < 1000; i++) { if (isprime[i]) { prime.Add(i); } }}// Function to get the number of// distinct ways to get sum// as K different primesstatic int CountWays(int i, int j, int sum, int n, int k){ // If index went out of prime // array size or the sum became // larger than n return 0 if (i >= prime.Count - 1 || sum > n) { return 0; } // If sum becomes equal to n and // j becomes exactly equal to k. // Return 1, else if j is still // not equal to k, return 0 if (sum == n) { if (j == k) { return 1; } return 0; } // If sum!=n and still j as // exceeded, return 0 if (j == k) return 0; // If that state is already // calculated, return directly // the ans if (dp[i, j, sum] != 0) return dp[i, j, sum]; int inc = 0, exc = 0; // Include the current prime inc = CountWays(i + 1, j + 1, sum + prime[i], n, k); // Exclude the current prime exc = CountWays(i + 1, j, sum, n, k); // Return by memoizing the ans return dp[i, j, sum] = inc + exc;}// Driver codestatic public void Main(){ // Precompute primes by sieve sieve(); int N = 100, K = 5; Console.WriteLine(CountWays(0, 0, 0, N, K));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to count the Number // of distinct ways to represent // a number as K different primes // Prime vector var prime = []; // Sieve array of prime var isprime = Array(1000).fill(true);// DP array var dp = Array.from(Array(200), ()=>Array(20));for(var i =0; i<200; i++) for(var j =0; j<20; j++) dp[i][j] = new Array(1000).fill(0);function sieve() { // Initialise all numbers // as prime // Sieve of Eratosthenes. for (var i = 2; i * i <= 1000; i++) { if (isprime[i]) { for (var j = i * i; j <= 1000; j += i) { isprime[j] = false; } } } // Push all the primes into // prime vector for (var i = 2; i <= 1000; i++) { if (isprime[i]) { prime.push(i); } } } // Function to get the number of // distinct ways to get sum // as K different primes function CountWays(i, j, sum, n, k) { // If index went out of prime // array size or the sum became // larger than n return 0 if (i > prime.length || sum > n) { return 0; } // If sum becomes equal to n and // j becomes exactly equal to k. // Return 1, else if j is still // not equal to k, return 0 if (sum == n) { if (j == k) { return 1; } return 0; } // If sum!=n and still j as // exceeded, return 0 if (j == k) return 0; // If that state is already // calculated, return directly // the ans if (dp[i][j][sum]) return dp[i][j][sum]; var inc = 0, exc = 0; // Include the current prime inc = CountWays(i + 1, j + 1, sum + prime[i], n, k); // Exclude the current prime exc = CountWays(i + 1, j, sum, n, k); // Return by memoizing the ans return dp[i][j][sum] = inc + exc; } // Driver code // Precompute primes by sieve sieve(); var N = 100, K = 5; document.write( CountWays(0, 0, 0, N, K)); </script> |
Output:
55
Time Complexity: O(N*K).
Auxiliary Space: O(20*200*1000).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
