在数组中插入最小值，以使数组总和成为质数 _数据结构

本文概述

C ++
Java
Python3
C#
PHP
C ++
Java
Python3
C#
PHP

给定n个整数数组。找到要插入数组的最小数目, 以便数组所有元素的和成为素数。如果sum已经是质数, 则返回0。
例子：

Input : arr[] = { 2, 4, 6, 8, 12 } Output : 5Input : arr[] = { 3, 5, 7 } Output : 0

简单的方法：解决此问题的最简单方法是首先找到数组元素的总和。然后检查此和是否为素数, 如果和为素数则返回零, 否则找到比该和大的素数。通过从(sum + 1)直到找到素数, 检查一个数字是否为素数, 我们可以找到大于素数的总和。一旦找到刚好大于和的质数, 则返回和与该质数的差。
下面是上述想法的实现：
C ++

//C++ program to find minimum number to //insert in array so their sum is prime #include < bits/stdc++.h> using namespace std; //function to check if a //number is prime or not bool isPrime( int n) { //Corner case if (n < = 1) return false ; //Check from 2 to n - 1 for ( int i = 2; i < n; i++) if (n % i == 0) return false ; return true ; }//Find prime number //greater than a number int findPrime( int n) { int num = n + 1; //find prime greater than n while (num) { //check if num is prime if (isPrime(num)) return num; //increment num num = num + 1; }return 0; }//To find number to be added //so sum of array is prime int minNumber( int arr[], int n) { int sum = 0; //To find sum of array elements for ( int i = 0; i < n; i++) sum += arr[i]; //if sum is already prime //return 0 if (isPrime(sum)) return 0; //To find prime number //greater than sum int num = findPrime(sum); //Return difference of //sum and num return num - sum; }//Driver code int main() { int arr[] = { 2, 4, 6, 8, 12 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < minNumber(arr, n); return 0; }

Java

//Java program to find minimum number to //insert in array so their sum is primeclass GFG { //function to check if a //number is prime or not static boolean isPrime( int n) { //Corner case if (n < = 1 ) return false ; //Check from 2 to n - 1 for ( int i = 2 ; i < n; i++) if (n % i == 0 ) return false ; return true ; }//Find prime number //greater than a number static int findPrime( int n) { int num = n + 1 ; //find prime greater than n while (num> 0 ) {//check if num is prime if (isPrime(num)) return num; //increment num num = num + 1 ; } return 0 ; }//To find number to be added //so sum of array is prime static int minNumber( int arr[], int n) { int sum = 0 ; //To find sum of array elements for ( int i = 0 ; i < n; i++) sum += arr[i]; //if sum is already prime //return 0 if (isPrime(sum)) return 0 ; //To find prime number //greater than sum int num = findPrime(sum); //Return difference of //sum and num return num - sum; }//Driver Code public static void main(String[]args) { int arr[] = { 2 , 4 , 6 , 8 , 12 }; int n = arr.length; System.out.println(minNumber(arr, n)); } }//This code is contributed by Azkia Anam.

Python3

# Python3 program to find minimum number to # insert in array so their sum is prime# function to check if a # number is prime or not def isPrime(n):# Corner case if n < = 1 : return False# Check from 2 to n - 1 for i in range ( 2 , n): if n % i = = 0 : return Falsereturn True# Find prime number # greater than a number def findPrime(n): num = n + 1# find prime greater than n while (num):# check if num is prime if isPrime(num): return num# Increment num num + = 1return 0# To find number to be added # so sum of array is prime def minNumber(arr): s = 0# To find sum of array elements for i in range ( 0 , len (arr)): s + = arr[i]# If sum is already prime # return 0 if isPrime(s) : return 0# To find prime number # greater than sum num = findPrime(s)# Return differnece of sum and num return num - s# Driver code arr = [ 2 , 4 , 6 , 8 , 12 ] print (minNumber(arr))# This code is contributed by Sachin Bisht

//C# program to find minimum number to //insert in array so their sum is prime using System; class GFG { //function to check if a //number is prime or not static bool isPrime( int n) { //Corner case if (n < = 1) return false ; //Check from 2 to n - 1 for ( int i = 2; i < n; i++) if (n % i == 0) return false ; return true ; }//Find prime number //greater than a number static int findPrime( int n) { int num = n + 1; //find prime greater than n while (num> 0) {//check if num is prime if (isPrime(num)) return num; //increment num num = num + 1; } return 0; }//To find number to be added //so sum of array is prime static int minNumber( int []arr, int n) { int sum = 0; //To find sum of array elements for ( int i = 0; i < n; i++) sum += arr[i]; //if sum is already prime //return 0 if (isPrime(sum)) return 0; //To find prime number //greater than sum int num = findPrime(sum); //Return difference of sum and num return num - sum; }//Driver Code public static void Main() { int []arr = { 2, 4, 6, 8, 12 }; int n = arr.Length; Console.Write(minNumber(arr, n)); } }//This code is contributed by nitin mittal

PHP

< ?php //PHP program to find minimum number to //insert in array so their sum is prime//function to check if a //number is prime or not function isPrime( $n ) {//Corner case if ( $n < = 1) return false; //Check from 2 to n - 1 for ( $i = 2; $i < $n ; $i ++) if ( $n % $i == 0) return false; return true; }//Find prime number //greater than a number function findPrime( $n ) { $num = $n + 1; //find prime greater than n while ( $num ) { //check if num is prime if (isPrime( $num )) return $num ; //increment num $num = $num + 1; }return 0; }//To find number to be added //so sum of array is prime function minNumber( $arr , $n ) { $sum = 0; //To find sum of array elements for ( $i = 0; $i < $n ; $i ++) $sum += $arr [ $i ]; //if sum is already prime //return 0 if (isPrime( $sum )) return 0; //To find prime number //greater than sum $num = findPrime( $sum ); //Return difference of //sum and num return $num - $sum ; }//Driver Code $arr = array (2, 4, 6, 8, 12); $n = sizeof( $arr ); echo minNumber( $arr , $n ); //This code is contributed by nitin mittal ?>

输出如下：

5

时间复杂度：O(N^2)
【在数组中插入最小值，以使数组总和成为质数】高效方法：我们可以通过有效地预先计算大型布尔数组来检查数字是否为质数来优化上述方法ant筛。生成所有素数后, 找到刚好大于和的素数并返回它们之间的差。
以下是此方法的实现：
C ++

//C++ program to find minimum number to //insert in array so their sum is prime #include < bits/stdc++.h> using namespace std; #define MAX 100005//Array to store primes bool isPrime[MAX]; //function to calculate primes //using sieve of eratosthenes void sieveOfEratostheneses() { memset (isPrime, true , sizeof (isPrime)); isPrime[1] = false ; for ( int i = 2; i * i < MAX; i++) { if (isPrime[i]) { for ( int j = 2 * i; j < MAX; j += i) isPrime[j] = false ; } } }//Find prime number //greater than a number int findPrime( int n) { int num = n + 1; //To return prime number //greater than n while (num) { //check if num is prime if (isPrime[num]) return num; //increment num num = num + 1; } return 0; }//To find number to be added //so sum of array is prime int minNumber( int arr[], int n) { //call sieveOfEratostheneses //to calculate primes sieveOfEratostheneses(); int sum = 0; //To find sum of array elements for ( int i = 0; i < n; i++) sum += arr[i]; if (isPrime[sum]) return 0; //To find prime number //greater then sum int num = findPrime(sum); //Return difference of //sum and num return num - sum; }//Driver Code int main() { int arr[] = { 2, 4, 6, 8, 12 }; int n = sizeof (arr) /sizeof (arr[0]); cout < < minNumber(arr, n); return 0; }

Java

//Java program to find minimum number to //insert in array so their sum is primeclass GFG { static int MAX = 100005 ; //Array to store primes static boolean [] isPrime = new boolean [MAX]; //function to calculate primes //using sieve of eratosthenes static void sieveOfEratostheneses() { isPrime[ 1 ] = true ; for ( int i = 2 ; i * i < MAX; i++) { if (!isPrime[i]) { for ( int j = 2 * i; j < MAX; j += i) isPrime[j] = true ; } } }//Find prime number greater //than a number static int findPrime( int n) { int num = n + 1 ; //To return prime number //greater than n while (num> 0 ) { //check if num is prime if (!isPrime[num]) return num; //increment num num = num + 1 ; } return 0 ; }//To find number to be added //so sum of array is prime static int minNumber( int arr[], int n) { //call sieveOfEratostheneses //to calculate primes sieveOfEratostheneses(); int sum = 0 ; //To find sum of array elements for ( int i = 0 ; i < n; i++) sum += arr[i]; if (!isPrime[sum]) return 0 ; //To find prime number //greater then sum int num = findPrime(sum); //Return difference of //sum and num return num - sum; }//Driver Code public static void main(String[] args) { int arr[] = { 2 , 4 , 6 , 8 , 12 }; int n = arr.length; System.out.println(minNumber(arr, n)); } }//This code is contributed by mits

Python3

# Python3 program to find minimum number to # insert in array so their sum is primeisPrime = [ 1 ] * 100005# function to calculate prime # using sieve of eratosthenes def sieveOfEratostheneses(): isPrime[ 1 ] = False i = 2 while i * i < 100005 : if (isPrime[i]): j = 2 * i while j < 100005 : isPrime[j] = False j + = i i + = 1 return# Find prime number # greater than a number def findPrime(n): num = n + 1# find prime greater than n while (num):# check if num is prime if isPrime[num]: return num# Increment num num + = 1return 0# To find number to be added # so sum of array is prime def minNumber(arr):# call sieveOfEratostheneses to # calculate primes sieveOfEratostheneses()s = 0# To find sum of array elements for i in range ( 0 , len (arr)): s + = arr[i]# If sum is already prime # return 0 if isPrime展开 = = True : return 0# To find prime number # greater than sum num = findPrime(s)# Return differnece of # sum and num return num - s# Driver code arr = [ 2 , 4 , 6 , 8 , 12 ] print (minNumber(arr))# This code is contributed by Sachin Bisht

//C# program to find minimum number to //insert in array so their sum is primeclass GFG { static int MAX = 100005; //Array to store primes static bool [] isPrime = new bool [MAX]; //function to calculate primes //using sieve of eratosthenes static void sieveOfEratostheneses() { isPrime[1] = true ; for ( int i = 2; i * i < MAX; i++) { if (!isPrime[i]) { for ( int j = 2 * i; j < MAX; j += i) isPrime[j] = true ; } } }//Find prime number greater //than a number static int findPrime( int n) { int num = n + 1; //To return prime number //greater than n while (num> 0) { //check if num is prime if (!isPrime[num]) return num; //increment num num = num + 1; } return 0; }//To find number to be added //so sum of array is prime static int minNumber( int [] arr, int n) { //call sieveOfEratostheneses //to calculate primes sieveOfEratostheneses(); int sum = 0; //To find sum of array elements for ( int i = 0; i < n; i++) sum += arr[i]; if (!isPrime[sum]) return 0; //To find prime number //greater then sum int num = findPrime(sum); //Return difference of //sum and num return num - sum; }//Driver Code public static void Main() { int [] arr = { 2, 4, 6, 8, 12 }; int n = arr.Length; System.Console.WriteLine(minNumber(arr, n)); } }//This code is contributed by mits

PHP

< ?php//PHP program to find minimum number to //insert in array so their sum is prime $MAX =100005; //function to calculate primes //using sieve of eratosthenes function sieveOfEratostheneses() { $isPrime = array_fill (true, $MAX , NULL); $isPrime [1] = false; for ( $i = 2; $i * $i < $MAX ; $i ++) { if ( $isPrime [ $i ]) { for ( $j = 2 * $i ; $j < $MAX ; $j += $i ) $isPrime [ $j ] = false; } } } //Find prime number //greater than a number function findPrime( $n ) { $num = $n + 1; //To return prime number //greater than n while ( $num ) { //check if num is prime if ( $isPrime [ $num ]) return $num ; //increment num $num = $num + 1; } return 0; } //To find number to be added //so sum of array is prime function minNumber(& $arr , $n ) { //call sieveOfEratostheneses //to calculate primes sieveOfEratostheneses(); $sum = 0; //To find sum of array elements for ( $i = 0; $i < $n ; $i ++) $sum += $arr [ $i ]; if ( $isPrime [ $sum ]) return 0; //To find prime number //greater then sum $num = findPrime( $sum ); //Return difference of //sum and num return $num - $sum ; } //Driver Code $arr = array ( 2, 4, 6, 8, 12 ); $n = sizeof( $arr ) /sizeof( $arr [0]); echo minNumber( $arr , $n ); return 0; ?>

输出如下：