Dada una array de números positivos, la tarea es calcular la diferencia absoluta entre el producto de números no primos y números primos.
Nota: 1 no es ni primo ni no primo.
Ejemplos :
Input : arr[] = {1, 3, 5, 10, 15, 7}
Output : 45
Explanation : Product of non-primes = 150
Product of primes = 105
Input : arr[] = {3, 4, 6, 7}
Output : 3
Enfoque ingenuo: una solución simple es atravesar la array y seguir verificando cada elemento si es primo o no. Si el número es primo, multiplíquelo al producto P2, que representa el producto de los primos; de lo contrario, verifique si no es 1, luego multiplíquelo al producto de los no primos, digamos P1. Después de atravesar toda la array, tome la diferencia absoluta entre los dos (P1-P2).
Complejidad de tiempo: O(N*sqrt(N))
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 verifique si el número está presente en el mapa hash. Luego, multiplique estos números al producto P2; de lo contrario, verifique si no es 1, luego multiplíquelo al producto P1. Después de atravesar toda la array, muestra la diferencia absoluta entre los dos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Absolute Difference
// between the Product of Non-Prime numbers
// and Prime numbers of an Array
#include <bits/stdc++.h>
using namespace std;
// Function to find the difference between
// the product of non-primes and the
// product of primes of an array.
int calculateDifference(int arr[], int n)
{
// 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] = 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;
}
}
// Store the product of primes in P1 and
// the product of non primes in P2
int P1 = 1, P2 = 1;
for (int i = 0; i < n; i++) {
if (prime[arr[i]]) {
// the number is prime
P1 *= arr[i];
}
else if (arr[i] != 1) {
// the number is non-prime
P2 *= arr[i];
}
}
// Return the absolute difference
return abs(P2 - P1);
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 10, 15, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Find the absolute difference
cout << calculateDifference(arr, n);
return 0;
}
Java
// Java program to find the Absolute Difference
// between the Product of Non-Prime numbers
// and Prime numbers of an Array
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
class GFG{
// Function to find the difference between
// the product of non-primes and the
// product of primes of an array.
public static int calculateDifference(int []arr, int n)
{
// Find maximum value in the array
int max_val = Arrays.stream(arr).max().getAsInt();
// 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];
Arrays.fill(prime, 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;
}
}
// Store the product of primes in P1 and
// the product of non primes in P2
int P1 = 1, P2 = 1;
for (int i = 0; i < n; i++) {
if (prime[arr[i]]) {
// the number is prime
P1 *= arr[i];
}
else if (arr[i] != 1) {
// the number is non-prime
P2 *= arr[i];
}
}
// Return the absolute difference
return Math.abs(P2 - P1);
}
// Driver Code
public static void main(String []args)
{
int[] arr = new int []{ 1, 3, 5, 10, 15, 7 };
int n = arr.length;
// Find the absolute difference
System.out.println(calculateDifference(arr, n));
System.exit(0);
}
}
// This code is contributed
// by Harshit Saini
Python3
# Python3 program to find the Absolute Difference # between the Product of Non-Prime numbers # and Prime numbers of an Array # Function to find the difference between # the product of non-primes and the # product of primes of an array. def calculateDifference(arr, n): # Find maximum value in the array max_val = max(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. prime = (max_val + 1) * [True] # Remaining part of SIEVE prime[0] = False prime[1] = False p = 2 while p * p <= max_val: # 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+1, p): prime[i] = False p += 1 # Store the product of primes in P1 and # the product of non primes in P2 P1 = 1 ; P2 = 1 for i in range(n): if prime[arr[i]]: # the number is prime P1 *= arr[i] elif arr[i] != 1: # the number is non-prime P2 *= arr[i] # Return the absolute difference return abs(P2 - P1) # Driver Code if __name__ == '__main__': arr = [ 1, 3, 5, 10, 15, 7 ] n = len(arr) # Find the absolute difference print(calculateDifference(arr, n)) # This code is contributed # by Harshit Saini
C#
// C# program to find the Absolute Difference
// between the Product of Non-Prime numbers
// and Prime numbers of an Array
using System;
using System.Linq;
class GFG{
// Function to find the difference between
// the product of non-primes and the
// product of primes of an array.
static int calculateDifference(int []arr, int n)
{
// Find maximum value in the array
int max_val = arr.Max();
// 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 = Enumerable.Repeat(true,
max_val+1).ToArray();
// 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;
}
}
// Store the product of primes in P1 and
// the product of non primes in P2
int P1 = 1, P2 = 1;
for (int i = 0; i < n; i++) {
if (prime[arr[i]]) {
// the number is prime
P1 *= arr[i];
}
else if (arr[i] != 1) {
// the number is non-prime
P2 *= arr[i];
}
}
// Return the absolute difference
return Math.Abs(P2 - P1);
}
// Driver Code
public static void Main()
{
int[] arr = new int []{ 1, 3, 5, 10, 15, 7 };
int n = arr.Length;
// Find the absolute difference
Console.WriteLine(calculateDifference(arr, n));
}
}
// This code is contributed
// by Harshit Saini
PHP
<?php
// PHP program to find the Absolute Difference
// between the Product of Non-Prime numbers
// and Prime numbers of an Array
// Function to find the difference between
// the product of non-primes and the
// product of primes of an array.
function calculateDifference($arr, $n){
// Find maximum value in the array
$max_val = max($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.
$prime = array_fill(0 ,$max_val ,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;
}
}
// Store the product of primes in P1 and
// the product of non primes in P2
$P1 = 1;
$P2 = 1;
for ($i = 0; $i < $n; $i++) {
if ($prime[$arr[$i]]) {
// the number is prime
$P1 *= $arr[$i];
}
else if ($arr[$i] != 1) {
// the number is non-prime
$P2 *= $arr[$i];
}
}
// Return the absolute difference
return abs($P2 - $P1);
}
// Driver Code
$arr = array( 1, 3, 5, 10, 15, 7 );
$n = count($arr, COUNT_NORMAL);
// Find the absolute difference
echo CalculateDifference($arr, $n);
// This code is contributed
// by Harshit Saini
?>
Javascript
<script>
// Javascript program to find the Absolute Difference
// between the Product of Non-Prime numbers
// and Prime numbers of an Array
// Function to find the difference between
// the product of non-primes and the
// product of primes of an array.
function calculateDifference(arr , n)
{
// Find maximum value in the array
var max_val = Math.max.apply(Math,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.
var prime = Array(max_val + 1).fill(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;
}
}
// Store the product of primes in P1 and
// the product of non primes in P2
var P1 = 1, P2 = 1;
for (i = 0; i < n; i++) {
if (prime[arr[i]]) {
// the number is prime
P1 *= arr[i];
} else if (arr[i] != 1) {
// the number is non-prime
P2 *= arr[i];
}
}
// Return the absolute difference
return Math.abs(P2 - P1);
}
// Driver Code
var arr = [ 1, 3, 5, 10, 15, 7 ];
var n = arr.length;
// Find the absolute difference
document.write(calculateDifference(arr, n));
// This code contributed by gauravrajput1
</script>
Producción:
45
Complejidad de tiempo: O(N * log(log(N))
Complejidad de espacio: O(MAX(N, max_val)), donde max_val es el valor máximo de un elemento en la array dada.
Publicación traducida automáticamente
Artículo escrito por imdhruvgupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA