Dada una array de n enteros. Encuentre el número mínimo que se insertará en la array, de modo que la suma de todos los elementos de la array se convierta en primo. Si sum ya es primo, devuelve 0.
Ejemplos:
Input : arr[] = { 2, 4, 6, 8, 12 }
Output : 5
Input : arr[] = { 3, 5, 7 }
Output : 0
Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar primero la suma de los elementos de la array. Luego verifique si esta suma es prima o no, si la suma es prima, devuelva cero; de lo contrario, encuentre un número primo mayor que esta suma. Podemos encontrar un número primo mayor que la suma comprobando si un número es primo o no desde (suma+1) hasta que encontremos un número primo. Una vez que se encuentra un número primo justo mayor que la suma, devuelve la diferencia de la suma y este número primo.
A continuación se muestra la implementación de la idea anterior:
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 difference 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
?>
Javascript
<script>
// Javascript 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 (let i = 2; i < n; i++)
if (n % i == 0)
return false;
return true;
}
// Find prime number
// greater than a number
function findPrime(n)
{
let 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
function minNumber(arr,n)
{
let sum = 0;
// To find sum of array elements
for (let 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
let num = findPrime(sum);
// Return difference of
// sum and num
return num - sum;
}
// Driver Code
let arr=[2, 4, 6, 8, 12 ];
let n = arr.length;
document.write(minNumber(arr, n));
//This code is contributed by avanitrachhadiya2155
</script>
Producción
5
Complejidad del Tiempo: O( N 2 )
Enfoque eficiente: podemos optimizar el enfoque anterior precalculando de manera eficiente una gran array booleana para verificar si un número es primo o no usando el tamiz de eratóstenes . Una vez que se generan todos los números primos, encuentre el número primo justo mayor que la suma y devuelva la diferencia entre ellos.
A continuación se muestra la implementación de este enfoque:
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[s] == True: return 0 # To find prime number # greater than sum num = findPrime(s) # Return difference 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;
?>
Javascript
<script>
// Javascript program to find minimum number to
// insert in array so their sum is prime
let MAX = 100005;
// Array to store primes
let isPrime = new Array(MAX).fill(0);
// function to calculate primes
// using sieve of eratosthenes
function sieveOfEratostheneses()
{
isPrime[1] = true;
for (let i = 2; i * i < MAX; i++)
{
if (!isPrime[i])
{
for (let j = 2 * i; j < MAX; j += i)
isPrime[j] = true;
}
}
}
// Find prime number greater
// than a number
function findPrime(n)
{
let 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
function minNumber(arr, n)
{
// call sieveOfEratostheneses
// to calculate primes
sieveOfEratostheneses();
let sum = 0;
// To find sum of array elements
for (let i = 0; i < n; i++)
sum += arr[i];
if (!isPrime[sum])
return 0;
// To find prime number
// greater then sum
let num = findPrime(sum);
// Return difference of
// sum and num
return num - sum;
}
// driver program
let arr = [ 2, 4, 6, 8, 12 ];
let n = arr.length;
document.write(minNumber(arr, n));
// This code is contributed by code_hunt.
</script>
Producción
5
Complejidad de tiempo: O(N log(log N))
Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA