找出要加到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 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

    推荐阅读