Dado un número entero N , la tarea es encontrar el número mínimo K que se sumará a N tal que N+K se convierta en un número primo .
Ejemplos:
Entrada: N = 10
Salida: 1
Explicación:
1 es el número mínimo que se suma a N tal que 10 + 1 = 11 es un número primo
Entrada: N = 20
Salida: 3
Planteamiento: La idea es comprobar si el número es primo o no incrementando el valor a sumar K en 1 en cada iteración. Por lo tanto, se pueden seguir los siguientes pasos para calcular la respuesta:
- Inicialmente, verifique si el número dado es primo o no . Si es así, entonces el valor a agregar (K) es 0.
- Ahora, en cada iteración, incrementa el valor de N en 1 y verifica si el número es primo o no. Sea M el primer valor en el que N se convierte en primo . Entonces, el valor mínimo que debe agregarse para hacer que N sea primo es M – N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum
// number to be added to N to
// make it a prime number
#include <bits/stdc++.h>
using namespace std;
// Function to check if a given number
// is a prime or not
bool isPrime(int n)
{
// Base cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// For all the remaining numbers, check if
// any number is a factor if the number
// or not
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
// If none of the above numbers are the
// factors for the number, then the
// given number is prime
return true;
}
// Function to return the smallest
// number to be added to make a
// number prime
int findSmallest(int N)
{
// Base case
if (N == 0)
return 2;
if (N == 1)
return 1;
int prime = N, counter = 0;
bool found = false;
// Loop continuously until isPrime returns
// true for a number greater than n
while (!found) {
if (isPrime(prime))
found = true;
else {
// If the number is not a prime, then
// increment the number by 1 and the
// counter which stores the number
// to be added
prime++;
counter++;
}
}
return counter;
}
// Driver code
int main()
{
int N = 10;
cout << findSmallest(N);
return 0;
}
Java
// Java program to find the minimum
// number to be added to N to
// make it a prime number
import java.util.*;
class GFG{
// Function to check if a given number
// is a prime or not
static boolean isPrime(int n)
{
// Base cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// For all the remaining numbers, check if
// any number is a factor if the number
// or not
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
// If none of the above numbers are the
// factors for the number, then the
// given number is prime
return true;
}
// Function to return the smallest
// number to be added to make a
// number prime
static int findSmallest(int N)
{
// Base case
if (N == 0)
return 2;
if (N == 1)
return 1;
int prime = N, counter = 0;
boolean found = false;
// Loop continuously until isPrime returns
// true for a number greater than n
while (!found) {
if (isPrime(prime))
found = true;
else {
// If the number is not a prime, then
// increment the number by 1 and the
// counter which stores the number
// to be added
prime++;
counter++;
}
}
return counter;
}
// Driver code
public static void main(String[] args)
{
int N = 10;
System.out.print(findSmallest(N));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python 3 program to find the minimum # number to be added to N to # make it a prime number # Function to check if a given number # is a prime or not def isPrime(n): # Base cases if (n <= 1): return False if (n <= 3): return True # This is checked so that we can skip # middle five numbers in below loop if (n % 2 == 0 or n % 3 == 0): return False # For all the remaining numbers, check if # any number is a factor if the number # or not i = 5 while (i * i <= n ): if (n % i == 0 or n % (i + 2) == 0): return False i += 6 # If none of the above numbers are the # factors for the number, then the # given number is prime return True # Function to return the smallest # number to be added to make a # number prime def findSmallest(N): # Base case if (N == 0): return 2 if (N == 1): return 1 prime , counter = N, 0 found = False # Loop continuously until isPrime returns # true for a number greater than n while (not found): if (isPrime(prime)): found = True else : # If the number is not a prime, then # increment the number by 1 and the # counter which stores the number # to be added prime += 1 counter += 1 return counter # Driver code if __name__ == "__main__": N = 10 print(findSmallest(N)) # This code is contributed by chitranayal
C#
// C# program to find the minimum
// number to be added to N to
// make it a prime number
using System;
class GFG{
// Function to check if a given number
// is a prime or not
static bool isPrime(int n)
{
// Base cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// For all the remaining numbers, check if
// any number is a factor if the number
// or not
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
// If none of the above numbers are the
// factors for the number, then the
// given number is prime
return true;
}
// Function to return the smallest
// number to be added to make a
// number prime
static int findSmallest(int N)
{
// Base case
if (N == 0)
return 2;
if (N == 1)
return 1;
int prime = N, counter = 0;
bool found = false;
// Loop continuously until isPrime returns
// true for a number greater than n
while (!found) {
if (isPrime(prime))
found = true;
else {
// If the number is not a prime, then
// increment the number by 1 and the
// counter which stores the number
// to be added
prime++;
counter++;
}
}
return counter;
}
// Driver code
public static void Main()
{
int N = 10;
Console.Write(findSmallest(N));
}
}
// This code is contributed by AbhiThakur
Javascript
<script>
// Javascript program to find the minimum
// number to be added to N to
// make it a prime number
// Function to check if a given number
// is a prime or not
function isPrime(n)
{
// Base cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
// For all the remaining numbers, check if
// any number is a factor if the number
// or not
for (var i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
// If none of the above numbers are the
// factors for the number, then the
// given number is prime
return true;
}
// Function to return the smallest
// number to be added to make a
// number prime
function findSmallest(N)
{
// Base case
if (N == 0)
return 2;
if (N == 1)
return 1;
var prime = N, counter = 0;
var found = false;
// Loop continuously until isPrime returns
// true for a number greater than n
while (!found)
{
if (isPrime(prime))
found = true;
else
{
// If the number is not a prime, then
// increment the number by 1 and the
// counter which stores the number
// to be added
prime++;
counter++;
}
}
return counter;
}
// Driver code
var N = 10;
document.write( findSmallest(N));
// This code is contributed by noob2000.
</script>
Producción:
1