Comprobar si la suma de primos es divisible por cualquier primo de la array

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 , 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 3

Entrada: 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 . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *