Dada una array arr[] , la tarea es comprobar si la suma de los números primos de la array es divisible por cualquiera de los números primos de la array. Si es así, escriba SÍ , de lo contrario, escriba NO .
Ejemplos:
Entrada: arr[] = {2, 3}
Salida: NO
Primos: 2, 3
Suma = 2 + 3 = 5 que no es divisible por 2 ni por 3Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: SÍ
2 + 3 + 5 = 10 es divisible tanto por 2 como por 5
Enfoque: La idea es generar todos los números primos hasta el máximo de elementos de la array utilizando Sieve of Eratosthenes .
- Recorra la array y verifique si el elemento actual es primo o no. Si es primo, actualice sum = sum + arr[i] .
- Recorra la array nuevamente y verifique si sum % arr[i] = 0 donde arr[i] es primo . Si es así, imprima SÍ . De lo contrario, escriba NO al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if sum of primes from an array
// is divisible by any of the primes from the same array
#include <bits/stdc++.h>
using namespace std;
// Function to print "YES" if sum of primes from an array
// is divisible by any of the primes from the same array
void SumDivPrime(int A[], int n)
{
int max_val = *(std::max_element(A, A + n)) + 1;
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
vector<bool> prime(max_val + 1, true);
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
int sum = 0;
// Traverse through the array
for (int i = 0; i < n; ++i) {
if (prime[A[i]])
sum += A[i];
}
for (int i = 0; i < n; ++i) {
if (prime[A[i]] && sum % A[i] == 0) {
cout << "YES";
return;
}
}
cout << "NO";
}
// Driver program
int main()
{
int A[] = { 1, 2, 3, 4, 5 };
int n = sizeof(A) / sizeof(A[0]);
SumDivPrime(A, n);
return 0;
}
Java
// Java program to check if sum of primes from an array
// is divisible by any of the primes from the same array
class Solution
{
//returns the maximum value
static int max_element(int A[])
{
int max=Integer.MIN_VALUE;
for(int i=0;i<A.length;i++)
if(max<A[i])
max=A[i];
return max;
}
// Function to print "YES" if sum of primes from an array
// is divisible by any of the primes from the same array
static void SumDivPrime(int A[], int n)
{
int max_val = (max_element(A)) + 1;
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
boolean prime[]=new boolean[max_val+1];
//initialize the array
for(int i=0;i<=max_val;i++)
prime[i]=true;
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
int sum = 0;
// Traverse through the array
for (int i = 0; i < n; ++i) {
if (prime[A[i]])
sum += A[i];
}
for (int i = 0; i < n; ++i) {
if (prime[A[i]] && sum % A[i] == 0) {
System.out.println( "YES");
return;
}
}
System.out.println("NO");
}
// Driver program
public static void main(String args[])
{
int A[] = { 1, 2, 3, 4, 5 };
int n = A.length;
SumDivPrime(A, n);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to check if sum of
# primes from an array is divisible
# by any of the primes from the same array
import math
# Function to print "YES" if sum of primes
# from an array is divisible by any of the
# primes from the same array
def SumDivPrime(A, n):
max_val = max(A) + 1
# USE SIEVE TO FIND ALL PRIME NUMBERS
# LESS THAN OR EQUAL TO max_val
# Create a boolean array "prime[0..n]".
# A value in prime[i] will finally be
# false if i is Not a prime, else true.
prime = [True] * (max_val + 1)
# Remaining part of SIEVE
prime[0] = False
prime[1] = False
for p in range(2, int(math.sqrt(max_val)) + 1):
# If prime[p] is not changed,
# then it is a prime
if prime[p] == True :
# Update all multiples of p
for i in range(2 * p, max_val + 1, p):
prime[i] = False
sum = 0
# Traverse through the array
for i in range(0, n):
if prime[A[i]]:
sum += A[i]
for i in range(0, n):
if prime[A[i]] and sum % A[i] == 0:
print("YES")
return
print("NO")
# Driver Code
A = [ 1, 2, 3, 4, 5 ]
n = len(A)
SumDivPrime(A, n)
# This code is contributed
# by saurabh_shukla
C#
// C# program to check if sum of primes
// from an array is divisible by any of
// the primes from the same array
class GFG
{
//returns the maximum value
static int max_element(int[] A)
{
int max = System.Int32.MinValue;
for(int i = 0; i < A.Length; i++)
if(max < A[i])
max = A[i];
return max;
}
// Function to print "YES" if sum of
// primes from an array is divisible
// by any of the primes from the same array
static void SumDivPrime(int[] A, int n)
{
int max_val = (max_element(A)) + 1;
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
bool[] prime=new bool[max_val+1];
//initialize the array
for(int i = 0; i <= max_val; i++)
prime[i] = true;
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= max_val; p++)
{
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
int sum = 0;
// Traverse through the array
for (int i = 0; i < n; ++i)
{
if (prime[A[i]])
sum += A[i];
}
for (int i = 0; i < n; ++i)
{
if (prime[A[i]] && sum % A[i] == 0)
{
System.Console.WriteLine( "YES");
return;
}
}
System.Console.WriteLine("NO");
}
// Driver code
public static void Main()
{
int []A = { 1, 2, 3, 4, 5 };
int n = A.Length;
SumDivPrime(A, n);
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to check if sum of primes
// from an array is divisible by any of
// the primes from the same array
// Function to print "YES" if sum of primes
// from an array is divisible by any of the
// primes from the same array
function SumDivPrime($A, $n)
{
$max_val = max($A);
// USE SIEVE TO FIND ALL PRIME NUMBERS
// LESS THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
$prime = array_fill(1, $max_val + 1, true);
// Remaining part of SIEVE
$prime[0] = false;
$prime[1] = false;
for ($p = 2; $p * $p <= $max_val; $p++)
{
// If prime[p] is not changed, then
// it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2;
$i <= $max_val; $i += $p)
$prime[$i] = false;
}
}
$sum = 0;
// Traverse through the array
for ($i = 0; $i < $n; ++$i)
{
if ($prime[$A[$i]])
$sum += $A[$i];
}
for ($i = 0; $i < $n; ++$i)
{
if ($prime[$A[$i]] &&
$sum % $A[$i] == 0)
{
echo "YES";
return;
}
}
echo "NO";
}
// Driver Code
$A = array( 1, 2, 3, 4, 5 );
$n = sizeof($A) ;
SumDivPrime($A, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to check if sum
// of primes from an array is divisible
// by any of the primes from the same array
// Returns the maximum value
function max_element(A)
{
var max = Number.MIN_VALUE;
for(var i = 0; i < A.length; i++)
if (max < A[i])
max = A[i];
return max;
}
// Function to print "YES" if sum of primes
// from an array is divisible by any of the
// primes from the same array
function SumDivPrime(A, n)
{
var max_val = (max_element(A)) + 1;
// USE SIEVE TO FIND ALL PRIME NUMBERS LESS
// THAN OR EQUAL TO max_val
// Create a boolean array "prime[0..n]". A
// value in prime[i] will finally be false
// if i is Not a prime, else true.
var prime = new Array(max_val + 1);
// Initialize the array
for(var i = 0; i <= max_val; i++)
prime[i] = true;
// Remaining part of SIEVE
prime[0] = false;
prime[1] = false;
for(var p = 2; p * p <= max_val; p++)
{
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for(var i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
var sum = 0;
// Traverse through the array
for(var i = 0; i < n; ++i)
{
if (prime[A[i]])
sum += A[i];
}
for(var i = 0; i < n; ++i)
{
if (prime[A[i]] && sum % A[i] == 0)
{
document.write("YES");
return;
}
}
document.write("NO");
}
// Driver code
var A = [ 1, 2, 3, 4, 5 ];
var n = A.length;
SumDivPrime(A, n);
// This code is contributed by SoumikMondal
</script>
Producción:
YES
Complejidad de tiempo: O(max_val*log(log(max_val))), donde max_val es el elemento más grande de la array.
Espacio Auxiliar: O(max_val)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA