找出要加到N的最小数字，使其成为质数

本文概述

• C ++
• Java
• Python3
• C#

给定整数N，任务是找出要加到N中的最小数K，使N + K成为质数。

例子：

输入：N = 10
输出：1
说明：
1是要加到N的最小数字, 使得10 +1 = 11是质数
输入：N = 20
输出：3

方法：这个想法是通过在每次迭代中将要添加的K值增加1来检查数字是否为质数。因此, 可以按照以下步骤计算答案：

1. 原来, 检查给定的数字是否为质数。如果是, 则要添加的值(K)为0。
2. 现在, 在每次迭代中, 增加ñby1并检查数字是否为素数。让第一个值在ñ成为素数中号。然后, 需要添加的最小值ñ素数是M – N.

下面是上述方法的实现：

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

输出如下：

1

---