Comprobar si un número se puede representar como la suma de K enteros positivos de los cuales al menos K – 1 son casi primos

Dados dos números enteros N y K , la tarea es verificar si N se puede representar como una suma de K números enteros positivos, donde al menos K – 1 de ellos son casi primos. 

Casi primos : se refiere a aquellos números que se pueden representar como un producto de cualquier par de números primos .

Ejemplos:

Entrada : N = 100, K = 6
Salida:
Explicación: 100 se puede representar como 4 + 6 + 9 + 10 + 14 + 57, donde 4 (= 2 * 2), 6 ( = 3 * 2), 9 ( = 3 * 3), 10 ( = 5 * 2) y 14 ( = 7 * 2) son casi primos.

Entrada : N=19, K = 4
Salida: No

Planteamiento: La idea es encontrar la suma de los primeros K – 1 números casi primos y verificar si su valor es menor o igual que N o no. Si se encuentra que es cierto, escriba . De lo contrario , imprima No.
Siga los pasos a continuación para resolver el problema:

  • Almacene la suma de los primeros K – 1 números casi primos en una variable, digamos S .
  • Iterar desde 2 , hasta obtener S y realizar los siguientes pasos:
  • Compruebe si el valor de S>=N. Si se encuentra que es cierto, escriba .
  • De lo contrario, imprima No.

A continuación se muestra la implementación del enfoque anterior:

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>
Producción: 

Yes

 

Complejidad temporal: O(K * √X), donde X es el (K – 1) número casi primo.
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por poulami21ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *