Suma de elementos de array que son factores primos de un número dado

Dada una array arr[] de tamaño N y un entero positivo K , la tarea es encontrar la suma de todos los elementos de la array que son factores primos de K .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 5, 6, 7, 15}, K = 35
Salida: 12
Explicación: De la array dada, 5 y 7 son factores primos de 35. Por lo tanto, la suma requerida = 5 + 7 = 12.

Entrada: arr[] = {1, 3, 5, 7}, K = 42
Salida: 10
Explicación: De la array dada, 3 y 7 son factores primos de 42. Por lo tanto, la suma requerida = 3 + 7 = 10.

Enfoque: La idea es atravesar la array y, para cada elemento de la array, verificar si es un factor primo de K o no. Agregue esos elementos a la suma, para los cuales se satisface la condición. Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos sum , para almacenar la suma requerida.
  • Recorra la array dada y, para cada elemento de la array, realice las siguientes operaciones:
  • Después de completar el recorrido de la array, imprima el valor de la suma como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is prime or not
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check if n is a
    // multiple of 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    // Above condition allows to check only
    // for every 6th number, starting from 5
    for (int i = 5; i * i <= n; i = i + 6)
 
        // If n is a multiple of i and i + 2
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to find the sum of array
// elements which are prime factors of K
void primeFactorSum(int arr[], int n, int k)
{
 
    // Stores the required sum
    int sum = 0;
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // If current element is a prime
        // factor of k, add it to the sum
        if (k % arr[i] == 0 && isPrime(arr[i])) {
            sum = sum + arr[i];
        }
    }
 
    // Print the result
    cout << sum;
}
 
// Driver Code
int main()
{
 
    // Given arr[]
    int arr[] = { 1, 2, 3, 5, 6, 7, 15 };
 
    // Store the size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int K = 35;
 
    primeFactorSum(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG
{
 
    // Function to check if a
    // number is prime or not
    static boolean isPrime(int n)
    {
       
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check if n is a
        // multiple of 2 or 3
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        // Above condition allows to check only
        // for every 6th number, starting from 5
        for (int i = 5; i * i <= n; i = i + 6)
 
            // If n is a multiple of i and i + 2
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to find the sum of array
    // elements which are prime factors of K
    static void primeFactorSum(int arr[], int n, int k)
    {
 
        // Stores the required sum
        int sum = 0;
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // If current element is a prime
            // factor of k, add it to the sum
            if (k % arr[i] == 0 && isPrime(arr[i]))
            {
                sum = sum + arr[i];
            }
        }
 
        // Print the result
        System.out.println(sum);
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        // Given arr[]
        int arr[] = { 1, 2, 3, 5, 6, 7, 15 };
 
        // Store the size of the array
        int N = arr.length;
        int K = 35;
        primeFactorSum(arr, N, K);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to check if a
# number is prime or not
def isPrime(n):
     
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True
 
    # Check if n is a
    # multiple of 2 or 3
    if (n % 2 == 0 or n % 3 == 0):
        return False
 
    # Above condition allows to check only
    # for every 6th number, starting from 5
    i = 5
     
    while (i * i <= n ):
 
        # If n is a multiple of i and i + 2
        if (n % i == 0 or n % (i + 2) == 0):
            return False
         
        i = i + 6
         
    return True
 
# Function to find the sum of array
# elements which are prime factors of K
def primeFactorSum(arr, n, k):
 
    # Stores the required sum
    sum = 0
 
    # Traverse the given array
    for i in range(n):
 
        # If current element is a prime
        # factor of k, add it to the sum
        if (k % arr[i] == 0 and isPrime(arr[i])):
            sum = sum + arr[i]
         
    # Print the result
    print(sum)
 
# Driver Code
 
# Given arr[]
arr = [ 1, 2, 3, 5, 6, 7, 15 ]
 
# Store the size of the array
N = len(arr)
 
K = 35
 
primeFactorSum(arr, N, K)
 
# This code is contributed by code_hunt

C#

// C# program for the above approach
using System;
 
class GFG
{
 
    // Function to check if a
    // number is prime or not
    static bool isPrime(int n)
    {
       
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // Check if n is a
        // multiple of 2 or 3
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        // Above condition allows to check only
        // for every 6th number, starting from 5
        for (int i = 5; i * i <= n; i = i + 6)
 
            // If n is a multiple of i and i + 2
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to find the sum of array
    // elements which are prime factors of K
    static void primeFactorSum(int []arr, int n, int k)
    {
 
        // Stores the required sum
        int sum = 0;
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // If current element is a prime
            // factor of k, add it to the sum
            if (k % arr[i] == 0 && isPrime(arr[i]))
            {
                sum = sum + arr[i];
            }
        }
 
        // Print the result
        Console.Write(sum);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
 
        // Given arr[]
        int []arr = { 1, 2, 3, 5, 6, 7, 15 };
 
        // Store the size of the array
        int N = arr.Length;
        int K = 35;
        primeFactorSum(arr, N, K);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to check if a
// number is prime or not
function isPrime(n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // Check if n is a
    // multiple of 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
     
    var i;
    // Above condition allows to check only
    // for every 6th number, starting from 5
    for (i = 5; i * i <= n; i = i + 6)
 
        // If n is a multiple of i and i + 2
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to find the sum of array
// elements which are prime factors of K
function primeFactorSum(arr, n, k)
{
 
    // Stores the required sum
    var sum = 0;
    var i;
    // Traverse the given array
    for (i = 0; i < n; i++) {
 
        // If current element is a prime
        // factor of k, add it to the sum
        if (k % arr[i] == 0 && isPrime(arr[i])) {
            sum = sum + arr[i];
        }
    }
 
    // Print the result
    document.write(sum);
}
 
// Driver Code
    // Given arr[]
    var arr = [1, 2, 3, 5, 6, 7, 15]
 
    // Store the size of the array
    var N = arr.length;
 
    var K = 35;
 
    primeFactorSum(arr, N, K);
 
</script>
Producción: 

12

 

Complejidad de tiempo: O(N*√X), donde X es el elemento más grande de la array
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Kingash 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 *