Encuentre el número mínimo que debe agregarse a N para convertirlo en un número primo

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:
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:
 

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: 
 

  1. Inicialmente, verifique si el número dado es primo o no . Si es así, entonces el valor a agregar (K) es 0.
  2. 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

 

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *