# Check if a number can be represented as sum of K positive integers out of which at least K – 1 are nearly prime

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.Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Examples:**

Input:N = 100, K = 6YesOutput: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.Explanation:100 can be represented as

: N=19, K = 4InputNoOutput:

**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 count of prime factors of the current number is equal to
- Check if the value of
**S>=N. I**f 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 number` `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 <= ` `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` `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` `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)` ` ` `cout << ` `"No"` `;` ` ` `// Otherwise, print Yes` ` ` `else` ` ` `cout << ` `"Yes"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `n = 100, k = 6;` ` ` `check(n, k);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `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)` ` ` `System.out.print(` `"No"` `);` ` ` `// Otherwise, print Yes` ` ` `else` ` ` `System.out.print(` `"Yes"` `);` `}` `// Driver Code` `public` `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 approach` `import` `math` `# Function to count all prime` `# factors of a given number` `def` `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 numbers` `def` `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 prime` `def` `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, prYes` ` ` `else` `:` ` ` `print` `(` `"Yes"` `)` `# Driver Code` `n ` `=` `100` `k ` `=` `6` `check(n, k)` ` ` `# This code is contributed by susmitakundugoaldanga.` |

## C#

`// C# program for above approach` `using` `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 number` `function` `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 numbers` `function` `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 prime` `function` `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 Code` `var` `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)