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

2021年5月1日17:27:32 发表评论 773 次浏览

## 本文概述

1是要加到N的最小数字, 使得10 +1 = 11是质数

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
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
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
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
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
prime++;
counter++;
}
}

return counter;
}

//Driver code
public static void Main()
{
int N = 10;

Console.Write(findSmallest(N));
}
}

//This code is contributed by AbhiThakur``````

``1`` 