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: Sí
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 Sí . 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:
- Comprueba si la cuenta de factores primos del número actual es igual a 2 o no.
- Si se encuentra que es cierto, agregue el valor del número actual a S .
- Si el conteo de tales números es igual a K – 1 , salga del bucle .
- Compruebe si el valor de S>=N. Si se encuentra que es cierto, escriba Sí .
- 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