Dada una array arr[] de N enteros positivos. La tarea es encontrar la suma de todos los elementos compuestos que son divisibles por un número k dado en la array dada.
Ejemplos:
Input: arr[] = {1, 3, 4, 5, 7}, k = 2
Output: 4, 4
There is one composite number i.e. 4.
So, sum = 4 and product = 4
Input: arr[] = {1, 2, 3, 4, 5, 6, 7}, k = 2
Output: 10, 24
There is only two composite numbers i.e. 4 and 6.
So, sum = 10 and product = 24
Enfoque ingenuo:
una solución simple es atravesar la array y seguir verificando cada elemento si es compuesto o no y también divisible por k, luego agregar y producir el elemento compuesto al mismo tiempo.
Enfoque eficiente:
genere todos los números primos hasta el elemento máximo de la array utilizando el tamiz de Eratóstenes y guárdelos en un hash. Ahora recorra la array y encuentre la suma y el producto de aquellos elementos que son compuestos y divisibles por k usando el tamiz.
A continuación se muestra la implementación del enfoque eficiente:
C++
// CPP program to find sum and product of
// composites which are divisible by k in given array.
#include <bits/stdc++.h>
using namespace std;
// Function to find count of composite
void compositeSumProduct(int arr[], int n, int k)
{
// Find maximum value in the array
int max_val = *max_element(arr, arr + n);
// 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] = true;
prime[1] = true;
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;
}
}
// Sum all primes in arr[]
int sum = 0, product = 1;
for (int i = 0; i < n; i++)
if (!prime[arr[i]] && arr[i] % k == 0) {
sum += arr[i];
product *= arr[i];
}
cout << "Sum of composite numbers divisible by k is "
<< sum;
cout << "\nProduct of composite numbers divisible by k is "
<< product;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
compositeSumProduct(arr, n, k);
return 0;
}
Java
// Java program to find sum and product of
// composites which are divisible by k in given array.
import java.util.Vector;
public class GFG {
static int max_val(int[] arr) {
int i;
// Initialize maximum element
int max = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Function to find count of composite
static void compositeSumProduct(int arr[], int n, int k) {
// Find maximum value in the array
int max_val = max_val(arr);
// 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<Boolean> prime = new Vector<>();
// Remaining part of SIEVE
for(int i = 0;i<max_val+1;i++){
prime.add(i, Boolean.TRUE);
}
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime.get(p) == true) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p) {
prime.add(i, Boolean.FALSE);
}
}
}
// Sum all primes in arr[]
int sum = 0, product = 1;
for (int i = 0; i < n; i++) {
//if (!prime[arr[i]] && arr[i] % k == 0)
if (!prime.get(arr[i]) && arr[i] % k == 0) {
sum += arr[i];
product *= arr[i];
}
}
System.out.println("Sum of composite numbers "
+ "divisible by k is " + sum);
System.out.println("\nProduct of composite numbers"
+ " divisible by k is " + product);
}
// Driver code
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = arr.length;
int k = 2;
compositeSumProduct(arr, n, k);
}
}
Python3
# Python 3 program to find sum and product
# of composites which are divisible by k
# in given array.
from math import sqrt, ceil
# Function to find count of composite
def compositeSumProduct(arr, n, k):
# Find maximum value in the array
max_val = arr[0];
for i in range(len(arr)):
if(max_val < arr[i]):
max_val = arr[i]
# 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 for i in range(max_val + 1)]
# Remaining part of SIEVE
k = int(sqrt(max_val))
for p in range(2, k + 1, 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(p * 2, max_val, p):
prime[i] = False
# Sum all primes in arr[]
sum = 0
product = 1
for i in range(0, n, 1):
if (prime[arr[i]] == False and
arr[i] % k == 0):
sum += arr[i]
product *= arr[i]
print("Sum of composite numbers",
"divisible by k is", sum)
print("Product of composite numbers",
"divisible by k is", product)
# Driver code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
k = 2
compositeSumProduct(arr, n, k)
# This code is contributed by
# Surendra_Gangwar
C#
// C# program to find sum and product of
// composites which are divisible by k in given array.
using System;
using System.Collections.Generic;
public class GFG {
static int max_val_func(int []arr) {
int i;
// Initialize maximum element
int max = arr[0];
// Traverse array elements from second and
// compare every element with current max
for (i = 1; i < arr.Length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Function to find count of composite
static void compositeSumProduct(int []arr, int n, int k) {
// Find maximum value in the array
int max_val = max_val_func(arr);
// 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.
List<int> prime = new List<int>();
// Remaining part of SIEVE
for(int i = 0;i<max_val+1;i++){
prime.Insert(i, 1);
}
for (int p = 2; p * p <= max_val; p++) {
// If prime[p] is not changed, then
// it is a prime
if (prime[p] == 1) {
// Update all multiples of p
for (int i = p * 2; i <= max_val; i += p) {
prime.Insert(i, 0);
}
}
}
// Sum all primes in arr[]
int sum = 0, product = 1;
for (int i = 0; i < n; i++) {
//if (!prime[arr[i]] && arr[i] % k == 0)
if (prime[arr[i]]==0 && arr[i] % k == 0) {
sum += arr[i];
product *= arr[i];
}
}
Console.WriteLine("Sum of composite numbers "
+ "divisible by k is " + sum);
Console.WriteLine("\nProduct of composite numbers"
+ " divisible by k is " + product);
}
// Driver code
static public void Main(String []args) {
int []arr = {1, 2, 3, 4, 5, 6, 7};
int n = arr.Length;
int k = 2;
compositeSumProduct(arr, n, k);
}
}
//contributed by Arnab Kundu
Javascript
<script>
// Javsacript program to find sum and product of
// composites which are divisible by k in given array.
// Function to find count of composite
function compositeSumProduct(arr, n, k)
{
// Find maximum value in the array
let max_val = arr.sort((a, b) => b - a)[0];
// 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.
let prime = new Array(max_val + 1).fill(true);
// Remaining part of SIEVE
prime[0] = true;
prime[1] = true;
for (let 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 (let i = p * 2; i <= max_val; i += p)
prime[i] = false;
}
}
// Sum all primes in arr[]
let sum = 0, product = 1;
for (let i = 0; i < n; i++)
if (!prime[arr[i]] && arr[i] % k == 0) {
sum += arr[i];
product *= arr[i];
}
document.write("Sum of composite numbers divisible by k is " + sum);
document.write("<br>Product of composite numbers divisible by k is " + product);
}
// Driver code
let arr = [1, 2, 3, 4, 5, 6, 7];
let n = arr.length
let k = 2;
compositeSumProduct(arr, n, k);
// This code is contributed by gfgking
</script>
Producción:
Sum of composite numbers divisible by k is 10 Product of composite numbers divisible by k is 24
Complejidad de tiempo: O(n), ya que estamos recorriendo n veces. Donde n es el valor máximo de un elemento en una array, no el tamaño.
Espacio auxiliar: O (MaxElement), ya que estamos usando una array principal de tamaño MaxElement.
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA