# 在数组中插入最小值，以使数组总和成为质数

2021年4月27日17:11:02 发表评论 733 次浏览

## 本文概述

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

Input : arr[] = { 3, 5, 7 }
Output : 0``````

## 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];

//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 prime

class 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];

//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 False

return 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 + = 1

return 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#

``````//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];

//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 ];

//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``

## 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 prime

class 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 prime

isPrime = [ 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 + = 1

return 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#

``````//C# program to find minimum number to
//insert in array so their sum is prime

class 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;
?>``````

``5``