Given two integers N and K, the task is to check if N can be represented as a sum of K positive integers, where at least K – 1 of them are nearly prime.
Nearly Primes: Refers to those numbers which can be represented as a product of any pair of prime numbers.
Examples:
Input: N = 100, K = 6
Output: Yes
Explanation: 100 can be represented as 4 + 6 + 9 + 10 + 14 + 57, where 4 (= 2 * 2), 6 ( = 3 * 2), 9 ( = 3 * 3), 10 ( = 5 * 2) and 14 ( = 7 * 2) are nearly primes.Input: N=19, K = 4
Output: No
Approach: The idea is to find the sum of the first K – 1 nearly prime numbers and check if its value is less than or equal to N or not. If found to be true, then print Yes. Otherwise, print No.
Follow the steps below to solve the problem:
- Store the sum of the first K – 1 nearly prime numbers in a variable, say S.
- Iterate from 2, until S is obtained and perform the following steps:
- Check if the count of prime factors of the current number is equal to 2 or not.
- If found to be true, add the value of the current number to S.
- If the count of such numbers is equal to K – 1, break out of the loop.
- Check if the value of S>=N. If found to be true, print Yes.
- Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count all prime// factors of a given numberint countPrimeFactors(int n){ int count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, // skip one element for (int i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return (count);}// Function to find the sum of// first n nearly prime numbersint findSum(int n){ // Store the required sum int sum = 0; for (int i = 1, num = 2; i <= n; num++) { // Add this number if it is // satisfies the condition if (countPrimeFactors(num) == 2) { sum += num; // Increment count of // nearly prime numbers i++; } } return sum;}// Function to check if N can be// represented as sum of K different// positive integers out of which at// least K - 1 of them are nearly primevoid check(int n, int k){ // Store the sum of first // K - 1 nearly prime numbers int s = findSum(k - 1); // If sum is greater // than or equal to n if (s >= n) cout << "No"; // Otherwise, print Yes else cout << "Yes";}// Driver Codeint main(){ int n = 100, k = 6; check(n, k); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count all prime// factors of a given numberstatic int countPrimeFactors(int n){ int count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, // skip one element for(int i = 3; i <= (int)Math.sqrt(n); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return (count);}// Function to find the sum of// first n nearly prime numbersstatic int findSum(int n){ // Store the required sum int sum = 0; for(int i = 1, num = 2; i <= n; num++) { // Add this number if it is // satisfies the condition if (countPrimeFactors(num) == 2) { sum += num; // Increment count of // nearly prime numbers i++; } } return sum;}// Function to check if N can be// represented as sum of K different// positive integers out of which at// least K - 1 of them are nearly primestatic void check(int n, int k){ // Store the sum of first // K - 1 nearly prime numbers int s = findSum(k - 1); // If sum is greater // than or equal to n if (s >= n) System.out.print("No"); // Otherwise, print Yes else System.out.print("Yes");}// Driver Codepublic static void main(String[] args){ int n = 100, k = 6; check(n, k);}}// This code is contributed by splevel62 |
Python3
# Python3 program for the above approachimport math# Function to count all prime# factors of a given numberdef countPrimeFactors(n) : count = 0 # Count the number of 2s # that divides n while (n % 2 == 0) : n = n // 2 count += 1 # Since n is odd at this point, # skip one element for i in range(3, int(math.sqrt(n) + 1), 2) : # While i divides n, count # i and divide n while (n % i == 0) : n = n // i count += 1 # If n is a prime number # greater than 2 if (n > 2) : count += 1 return (count)# Function to find the sum of# first n nearly prime numbersdef findSum(n) : # Store the required sum sum = 0 i = 1 num = 2 while(i <= n) : # Add this number if it is # satisfies the condition if (countPrimeFactors(num) == 2) : sum += num # Increment count of # nearly prime numbers i += 1 num += 1 return sum# Function to check if N can be# represented as sum of K different# positive integers out of which at# least K - 1 of them are nearly primedef check(n, k) : # Store the sum of first # K - 1 nearly prime numbers s = findSum(k - 1) # If sum is great # than or equal to n if (s >= n) : print("No") # Otherwise, print Yes else : print("Yes")# Driver Coden = 100k = 6check(n, k) # This code is contributed by susmitakundugoaldanga. |
C#
// C# program for above approachusing System;public class GFG { // Function to count all prime // factors of a given number static int countPrimeFactors(int n) { int count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, // skip one element for(int i = 3; i <= (int)Math.Sqrt(n); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return (count); } // Function to find the sum of // first n nearly prime numbers static int findSum(int n) { // Store the required sum int sum = 0; for(int i = 1, num = 2; i <= n; num++) { // Add this number if it is // satisfies the condition if (countPrimeFactors(num) == 2) { sum += num; // Increment count of // nearly prime numbers i++; } } return sum; } // Function to check if N can be // represented as sum of K different // positive integers out of which at // least K - 1 of them are nearly prime static void check(int n, int k) { // Store the sum of first // K - 1 nearly prime numbers int s = findSum(k - 1); // If sum is greater // than or equal to n if (s >= n) Console.WriteLine("No"); // Otherwise, print Yes else Console.WriteLine("Yes"); } // Driver code public static void Main(String[] args) { int n = 100, k = 6; check(n, k); }}// This code is contributed by splevel62. |
Javascript
<script>// Javascript program for the above approach// Function to count all prime// factors of a given numberfunction countPrimeFactors(n) { var count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = parseInt(n / 2); count++; } // Since n is odd at this point, // skip one element for(i = 3; i <= parseInt(Math.sqrt(n)); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = parseInt(n / i); count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return (count);}// Function to find the sum of// first n nearly prime numbersfunction findSum(n) { // Store the required sum var sum = 0; for(i = 1, num = 2; i <= n; num++) { // Add this number if it is // satisfies the condition if (countPrimeFactors(num) == 2) { sum += num; // Increment count of // nearly prime numbers i++; } } return sum;}// Function to check if N can be// represented as sum of K different// positive integers out of which at// least K - 1 of them are nearly primefunction check(n, k){ // Store the sum of first // K - 1 nearly prime numbers var s = findSum(k - 1); // If sum is greater // than or equal to n if (s >= n) document.write("No"); // Otherwise, print Yes else document.write("Yes");}// Driver Codevar n = 100, k = 6;check(n, k);// This code is contributed by todaysgaurav</script> |
Output
Yes
Time Complexity: O(K * √X), where X is the (K – 1)th nearly prime number.
Auxiliary Space: O(1)
Approach 2: Dynamic Programming:
Dynamic programming (DP) is used in the given code to efficiently calculate the sum of the first N nearly prime numbers.
- The idea behind DP is to store the solutions to subproblems and reuse them as needed to solve larger problems. In this case, the subproblem is finding the sum of the first k nearly prime numbers, where k is less than N. Once we have solved this subproblem, we can use the solution to compute the sum of the first k+1 nearly prime numbers, and so on until we have computed the sum of the first N nearly prime numbers.
- The DP array is represented by the vector dp, which has size N+1 and is initialized with -1 values. The value of dp[N] stores the sum of the first N nearly prime numbers. If dp[N] is already calculated, we can return it directly without recomputing it. Otherwise, we compute dp[N] recursively by first calculating dp[N-1], then checking if N*2-1 is nearly prime, and adding it to dp[N-1] if it is. Finally, we update dp[N] with the computed value and return it.
- Using DP in this way avoids recomputing the sum of the first k nearly prime numbers multiple times for different values of k, which can be computationally expensive. Instead, we only need to compute each value once and store it for later use. This significantly improves the efficiency of the algorithm.
Here is the Code of Above Approach:
C++
#include<bits/stdc++.h>using namespace std;// Function to count all prime// factors of a given numberint countPrimeFactors(int n){ int count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, // skip one element for (int i = 3; i <= sqrt(n); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return (count);}// Function to find the sum of// first n nearly prime numbersint findSum(int n, vector<int>& dp){ // If n is already calculated if (dp[n] != -1) return dp[n]; // If n is 0, return 0 if (n == 0) return 0; // If n is 1, return 2 if (n == 1) return 2; // Calculate the sum recursively int sum = findSum(n-1, dp); if (countPrimeFactors(n*2-1) == 2) sum += n*2-1; // Update the DP array dp[n] = sum; return sum;}// Function to check if N can be// represented as sum of K different// positive integers out of which at// least K - 1 of them are nearly primevoid check(int n, int k){ // Initialize the DP array vector<int> dp(n+1, -1); // Store the sum of first // K - 1 nearly prime numbers int s = findSum(k - 1, dp); // If sum is greater // than or equal to n if (s >= n) cout << "No"; // Otherwise, print Yes else cout << "Yes";}// Driver Codeint main(){ int n = 100, k = 6; check(n, k); return 0;} |
Java
import java.util.*;public class NearlyPrimeSum { // Function to count all prime factors of a given number static int countPrimeFactors(int n) { int count = 0; // Count the number of 2s that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, skip one element for (int i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n, count i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number greater than 2 if (n > 2) count++; return count; } // Function to find the sum of first n nearly prime numbers static int findSum(int n, int[] dp) { // If n is already calculated if (dp[n] != -1) return dp[n]; // If n is 0, return 0 if (n == 0) return 0; // If n is 1, return 2 if (n == 1) return 2; // Calculate the sum recursively int sum = findSum(n - 1, dp); if (countPrimeFactors(n * 2 - 1) == 2) sum += n * 2 - 1; // Update the DP array dp[n] = sum; return sum; } // Function to check if N can be represented as sum of K different positive integers // out of which at least K - 1 of them are nearly prime static void check(int n, int k) { // Initialize the DP array int[] dp = new int[n + 1]; Arrays.fill(dp, -1); // Store the sum of first K - 1 nearly prime numbers int s = findSum(k - 1, dp); // If sum is greater than or equal to n if (s >= n) System.out.println("No"); else System.out.println("Yes"); } // Driver Code public static void main(String[] args) { int n = 100, k = 6; check(n, k); }}// This code is contributed by chinmaya121221 |
Python3
import math# Function to count all prime# factors of a given numberdef count_prime_factors(n): count = 0 # Count the number of 2s # that divide n while n % 2 == 0: n //= 2 count += 1 # Since n is odd at this point, # skip one element for i in range(3, int(math.sqrt(n)) + 1, 2): # While i divides n, count i and divide n while n % i == 0: n //= i count += 1 # If n is a prime number greater than 2 if n > 2: count += 1 return count# Function to find the sum of# first n nearly prime numbersdef find_sum(n, dp): # If n is already calculated if dp[n] != -1: return dp[n] # If n is 0, return 0 if n == 0: return 0 # If n is 1, return 2 if n == 1: return 2 # Calculate the sum recursively sum = find_sum(n - 1, dp) if count_prime_factors(n * 2 - 1) == 2: sum += n * 2 - 1 # Update the DP array dp[n] = sum return sum# Function to check if N can be# represented as the sum of K different# positive integers out of which at# least K - 1 of them are nearly primedef check(n, k): # Initialize the DP array dp = [-1] * (n + 1) # Store the sum of first # K - 1 nearly prime numbers s = find_sum(k - 1, dp) # If the sum is greater than or equal to n if s >= n: print("No") # Otherwise, print Yes else: print("Yes")# Driver Codeif __name__ == "__main__": n = 100 k = 6 check(n, k) # This code is contributed by rambabuguphka |
C#
using System;using System.Collections.Generic;class Program{ // Function to count all prime // factors of a given number static int CountPrimeFactors(int n) { int count = 0; // Count the number of 2s // that divides n while (n % 2 == 0) { n = n / 2; count++; } // Since n is odd at this point, // skip one element for (int i = 3; i <= Math.Sqrt(n); i = i + 2) { // While i divides n, count // i and divide n while (n % i == 0) { n = n / i; count++; } } // If n is a prime number // greater than 2 if (n > 2) count++; return count; } // Function to find the sum of // first n nearly prime numbers static int FindSum(int n, List<int> dp) { // If n is already calculated if (dp[n] != -1) return dp[n]; // If n is 0, return 0 if (n == 0) return 0; // If n is 1, return 2 if (n == 1) return 2; // Calculate the sum recursively int sum = FindSum(n - 1, dp); if (CountPrimeFactors(n * 2 - 1) == 2) sum += n * 2 - 1; // Update the DP array dp[n] = sum; return sum; } // Function to check if N can be // represented as sum of K different // positive integers out of which at // least K - 1 of them are nearly prime static void Check(int n, int k) { // Initialize the DP array List<int> dp = new List<int>(new int[n + 1]); for (int i = 0; i <= n; i++) { dp[i] = -1; } // Store the sum of first // K - 1 nearly prime numbers int s = FindSum(k - 1, dp); // If sum is greater // than or equal to n if (s >= n) Console.WriteLine("No"); // Otherwise, print Yes else Console.WriteLine("Yes"); } // Driver Code static void Main() { int n = 100, k = 6; Check(n, k); }} |
Javascript
// Function to count all prime factors of a given numberfunction countPrimeFactors(n) { let count = 0; // Count the number of 2s that divide n while (n % 2 === 0) { n = Math.floor(n / 2); count++; } // Since n is odd at this point, skip one element for (let i = 3; i <= Math.sqrt(n); i += 2) { // While i divides n, count i and divide n while (n % i === 0) { n = Math.floor(n / i); count++; } } // If n is a prime number greater than 2 if (n > 2) { count++; } return count;}// Function to find the sum of first n nearly prime numbersfunction findSum(n, dp) { // If n is already calculated if (dp[n] !== -1) { return dp[n]; } // If n is 0, return 0 if (n === 0) { return 0; } // If n is 1, return 2 if (n === 1) { return 2; } // Calculate the sum recursively let sum = findSum(n - 1, dp); if (countPrimeFactors(n * 2 - 1) === 2) { sum += n * 2 - 1; } // Update the DP array dp[n] = sum; return sum;}// Function to check if N can be represented as the sum of K different positive integers// out of which at least K - 1 of them are nearly primefunction check(n, k) { // Initialize the DP array let dp = new Array(n + 1).fill(-1); // Store the sum of the first K - 1 nearly prime numbers let s = findSum(k - 1, dp); // If the sum is greater than or equal to n if (s >= n) { console.log("No"); } else { console.log("Yes"); }}// Driver Codeconst n = 100;const k = 6;check(n, k); |
Output
Yes
Time Complexity: O(n^2 * sqrt(n)), where n is the nearly prime number.
Auxiliary Space: O(n), where n is the size of the DP array.
Approach:
- This approach checks if a number is prime by iterating up to the square root of the number and checks for divisibility.
- The countPrimeFactors function counts the number of prime factors of a given number.
- The findSum function generates the first n nearly prime numbers and calculates their sum.
- Finally, the check function compares the sum with the given number to determine if it can be represented as a sum of K different positive integers, with at least K – 1 of them being nearly prime.
Here is the code of above approach:
C++
#include <iostream>#include <vector>#include <cmath>using namespace std;// Function to check if a number is primebool isPrime(int num) { if (num < 2) return false; for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) return false; } return true;}// Function to count all prime factors of a given numberint countPrimeFactors(int n) { int count = 0; for (int i = 2; i <= n; i++) { if (isPrime(i) && n % i == 0) count++; } return count;}// Function to find the sum of first n nearly prime numbersint findSum(int n) { vector<int> nearlyPrimes; int num = 2; while (nearlyPrimes.size() < n) { if (countPrimeFactors(num) == 2) nearlyPrimes.push_back(num); num++; } int sum = 0; for (int i = 0; i < n; i++) sum += nearlyPrimes[i]; return sum;}// Function to check if N can be represented as sum of K different positive integers// out of which at least K - 1 of them are nearly primevoid check(int n, int k) { // Store the sum of first K - 1 nearly prime numbers int s = findSum(k - 1); // If sum is greater than or equal to n if (s >= n) cout << "No"; // Otherwise, print Yes else cout << "Yes";}// Driver Codeint main() { int n = 100, k = 6; check(n, k); return 0;} |
Java
import java.util.ArrayList;public class NearlyPrime { // Function to check if a number is prime static boolean isPrime(int num) { if (num < 2) return false; for (int i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) return false; } return true; } // Function to count all prime factors of a given number static int countPrimeFactors(int n) { int count = 0; for (int i = 2; i <= n; i++) { if (isPrime(i) && n % i == 0) count++; } return count; } // Function to find the sum of first n nearly prime numbers static int findSum(int n) { ArrayList<Integer> nearlyPrimes = new ArrayList<>(); int num = 2; while (nearlyPrimes.size() < n) { if (countPrimeFactors(num) == 2) nearlyPrimes.add(num); num++; } int sum = 0; for (int i = 0; i < n; i++) sum += nearlyPrimes.get(i); return sum; } // Function to check if N can be represented as the sum of K different positive integers // out of which at least K - 1 of them are nearly prime static void check(int n, int k) { // Store the sum of first K - 1 nearly prime numbers int s = findSum(k - 1); // If sum is greater than or equal to n if (s >= n) System.out.println("No"); // Otherwise, print Yes else System.out.println("Yes"); } // Driver Code public static void main(String[] args) { int n = 100, k = 6; check(n, k); }} |
Python
import math# Function to check if a number is primedef is_prime(num): if num < 2: return False for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return True# Function to count all prime factors of a given numberdef count_prime_factors(n): count = 0 for i in range(2, n + 1): if is_prime(i) and n % i == 0: count += 1 return count# Function to find the sum of first n nearly prime numbersdef find_sum(n): nearly_primes = [] num = 2 while len(nearly_primes) < n: if count_prime_factors(num) == 2: nearly_primes.append(num) num += 1 sum_ = sum(nearly_primes[:n]) return sum_# Function to check if N can be represented as the sum of K different positive integers# out of which at least K - 1 of them are nearly primedef check(n, k): # Store the sum of first K - 1 nearly prime numbers s = find_sum(k - 1) # If the sum is greater than or equal to n, print "No" if s >= n: print("No") # Otherwise, print "Yes" else: print("Yes")# Driver Codeif __name__ == "__main__": n = 100 k = 6 check(n, k) |
C#
using System;using System.Collections.Generic;class Program{ // Function to check if a number is prime static bool IsPrime(int num) { if (num < 2) return false; for (int i = 2; i <= Math.Sqrt(num); i++) { if (num % i == 0) return false; } return true; } // Function to count all prime factors of a given number static int CountPrimeFactors(int n) { int count = 0; for (int i = 2; i <= n; i++) { if (IsPrime(i) && n % i == 0) count++; } return count; } // Function to find the sum of first n nearly prime numbers static int FindSum(int n) { List<int> nearlyPrimes = new List<int>(); int num = 2; while (nearlyPrimes.Count < n) { if (CountPrimeFactors(num) == 2) nearlyPrimes.Add(num); num++; } int sum = 0; for (int i = 0; i < n; i++) sum += nearlyPrimes[i]; return sum; } // Function to check if N can be represented as the sum of K different positive integers // out of which at least K - 1 of them are nearly prime static void Check(int n, int k) { // Store the sum of the first K - 1 nearly prime numbers int s = FindSum(k - 1); // If the sum is greater than or equal to n if (s >= n) Console.WriteLine("No"); // Otherwise, print Yes else Console.WriteLine("Yes"); } // Driver Code static void Main() { int n = 100, k = 6; Check(n, k); }} |
Javascript
// JavaScript program for the above approach// Function to check if a number is primefunction isPrime(num) { if (num < 2) return false; for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) return false; } return true;}// Function to count all prime factors of a given numberfunction countPrimeFactors(n) { let count = 0; for (let i = 2; i <= n; i++) { if (isPrime(i) && n % i === 0) count++; } return count;}// Function to find the sum of first n nearly prime numbersfunction findSum(n) { const nearlyPrimes = []; let num = 2; while (nearlyPrimes.length < n) { if (countPrimeFactors(num) === 2) nearlyPrimes.push(num); num++; } const sum = nearlyPrimes.reduce((acc, current) => acc + current, 0); return sum;}// Function to check if N can be represented as the sum of K different positive integers// out of which at least K - 1 of them are nearly primefunction check(n, k) { // Store the sum of the first K - 1 nearly prime numbers const s = findSum(k - 1); // If the sum is greater than or equal to n, print "No"; otherwise, print "Yes" console.log(s >= n ? "No" : "Yes");}// Driver Codeconst n = 100, k = 6;check(n, k);// This code is contributed by Susobhan Akhuli |
Output:
Yes
Time Complexity: O(K * √X), where X is the (K – 1)th nearly prime number.
Auxiliary Space: O(1)
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!
