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

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

本文概述

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

例子 ：

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

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

时间复杂度：O(N log(log N))

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: