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:
- Compruebe si el elemento de la array es un factor primo de K o no.
- Si se encuentra que es cierto, agregue el elemento actual a la suma .
- 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)