本文概述
- C ++
- Java
- Python3
- C#
例子:
输入:N = 10方法:这个想法是通过在每次迭代中将要添加的K值增加1来检查数字是否为质数。因此, 可以按照以下步骤计算答案:
输出:1
说明:
1是要加到N的最小数字, 使得10 +1 = 11是质数
输入:N = 20
输出:3
- 原来, 检查给定的数字是否为质数。如果是, 则要添加的值(K)为0。
- 现在, 在每次迭代中, 增加?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 1prime , 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 = 10print (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
【找出要加到N的最小数字,使其成为质数】输出如下:
1
推荐阅读
- 使用图查找链表中的循环长度
- ADP印度面试经验|S1(针对会员技术人员)
- 给定操作生成的质因子求和序列的最大长度
- 计算可能的长度为N的二进制字符串,而没有P个连续的0和Q个连续的1
- Salesforce面试经验|校园内
- 查找未排序数组中缺失的最小正数|S1
- Lex程序可计算行,空格和制表符的数量
- Win7可以不激活吗?Win7不激活会怎样样?
- spoon.sys损坏后,win7开机无法进入系统的处理办法