Dado un entero positivo N mayor que 1, la tarea es encontrar la cuenta mínima de Números Primos cuya suma sea igual a N dado .
Ejemplos:
Entrada: N = 100
Salida: 2
Explicación:
100 se puede escribir como la suma de 2 números primos 97 y 3.
Entrada: N = 25
Salida: 2
Explicación:
25 se puede escribir como la suma de 2 números primos 23 y 2.
Enfoque:
para el número mínimo de primos cuya suma es el número dado N , los números primos deben ser tan grandes como sea posible. Las siguientes son las observaciones para el enunciado del problema anterior:
- Caso 1: si el número es primo, entonces los números primos mínimos necesarios para hacer la suma N son 1 .
- Caso 2: si el número es par, entonces se puede expresar como una suma de dos números primos según la conjetura de Goldbach para cada número par mayor que 2. Por lo tanto, el número primo mínimo requerido para hacer la suma N es 2 .
- Caso 3: Si el número es impar:
- Si (N-2) es primo, entonces el número primo mínimo requerido para hacer la suma N dada es 2 .
- De lo contrario, los números primos mínimos requeridos para hacer la suma dada N son 3 porque:
As N is odd, then (N - 3) is even. Hence As per case 2: The minimum prime number required to make the sum (N-3) is 2. Therefore, The minimum prime number required to make the sum N is 3(2+1).
A continuación se muestran los pasos:
- Verifique si el número N dado es primo o no, usando el enfoque discutido en este artículo. En caso afirmativo, imprima 1 .
- De lo contrario, según los casos anteriores, imprima el número mínimo de números primos necesarios para hacer la suma N dada .
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 check if n is prime
bool isPrime(int n)
{
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to count the minimum
// prime required for given sum N
void printMinCountPrime(int N)
{
int minCount;
// Case 1:
if (isPrime(N)) {
minCount = 1;
}
// Case 2:
else if (N % 2 == 0) {
minCount = 2;
}
// Case 3:
else {
// Case 3a:
if (isPrime(N - 2)) {
minCount = 2;
}
// Case 3b:
else {
minCount = 3;
}
}
cout << minCount << endl;
}
// Driver Code
int main()
{
int N = 100;
// Function Call
printMinCountPrime(N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to check if n is prime
static boolean isPrime(int n)
{
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to count the minimum
// prime required for given sum N
static void printMinCountPrime(int N)
{
int minCount;
// Case 1:
if (isPrime(N)) {
minCount = 1;
}
// Case 2:
else if (N % 2 == 0) {
minCount = 2;
}
// Case 3:
else {
// Case 3a:
if (isPrime(N - 2)) {
minCount = 2;
}
// Case 3b:
else {
minCount = 3;
}
}
System.out.print(minCount +"\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 100;
// Function Call
printMinCountPrime(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to check if n is prime def isPrime(n) : for i in range(2, int(n ** (1/2)) + 1) : if (n % i == 0) : return False; return True; # Function to count the minimum # prime required for given sum N def printMinCountPrime(N) : # Case 1: if (isPrime(N)) : minCount = 1; # Case 2: elif (N % 2 == 0) : minCount = 2; # Case 3: else : # Case 3a: if (isPrime(N - 2)) : minCount = 2; # Case 3b: else : minCount = 3; print(minCount) ; # Driver Code if __name__ == "__main__" : N = 100; # Function Call printMinCountPrime(N); # This code is contributed by AnkitRai01
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if n is prime
static bool isPrime(int n)
{
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to count the minimum
// prime required for given sum N
static void printMinCountPrime(int N)
{
int minCount;
// Case 1:
if (isPrime(N)) {
minCount = 1;
}
// Case 2:
else if (N % 2 == 0) {
minCount = 2;
}
// Case 3:
else {
// Case 3a:
if (isPrime(N - 2)) {
minCount = 2;
}
// Case 3b:
else {
minCount = 3;
}
}
Console.WriteLine(minCount +"\n");
}
// Driver Code
public static void Main(string[] args)
{
int N = 100;
// Function Call
printMinCountPrime(N);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript program for the above approach
// Function to check if n is prime
function isPrime(n)
{
for (let i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to count the minimum
// prime required for given sum N
function printMinCountPrime(N)
{
let minCount;
// Case 1:
if (isPrime(N)) {
minCount = 1;
}
// Case 2:
else if (N % 2 == 0) {
minCount = 2;
}
// Case 3:
else {
// Case 3a:
if (isPrime(N - 2)) {
minCount = 2;
}
// Case 3b:
else {
minCount = 3;
}
}
document.write(minCount + "<br>");
}
// Driver Code
let N = 100;
// Function Call
printMinCountPrime(N);
// This code is contributed by gfgking
</script>
Producción:
2
Complejidad temporal: O(√N), donde N es el número dado.