Suma de elementos cuyos factores primos están presentes en el arreglo

Dada una array arr[] de enteros no negativos donde 2 ≤ arr[i] ≤ 10 ⁶ . La tarea es encontrar la suma de todos aquellos elementos de la array cuyos factores primos están presentes en la misma array. Ejemplos:

Entrada: arr[] = {2, 3, 10} Salida: 5 El factor de 2 es 2 que está presente en la array El factor de 3 es 3, también presente en la array Los factores de 10 son 2 y 5, de los cuales solo 2 está presente en la array. Entonces, suma = 2 + 3 = 5 Entrada: arr[] = {5, 11, 55, 25, 100} Salida: 96

Enfoque: la idea es calcular primero el factor primo mínimo hasta el elemento máximo de la array con factorización prima usando Sieve .

1. Ahora, itere la array y para un elemento arr[i]
2. Si arr[i] != 1 :
   • Si lessPrimeFactor(arr[i]) está presente en la array, actualice arr[i] / lessPrimeFactor(arr[i]) y vaya al paso 2.
   • De lo contrario, vaya al paso 1.
3. De lo contrario, actualice sum = sum + originalVal(arr[i]) .
4. Imprime la suma al final.

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

// C++ program to find the sum of the elements of an array
// whose prime factors are present in the same array
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 1000001
 
// Stores smallest prime factor for every number
int spf[MAXN];
 
// Function to calculate SPF (Smallest Prime Factor)
// for every number till MAXN
void sieve()
{
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)
 
        // Marking smallest prime factor for every
        // number to be itself.
        spf[i] = i;
 
    // Separately marking spf for every even
    // number as 2
    for (int i = 4; i < MAXN; i += 2)
        spf[i] = 2;
 
    for (int i = 3; i * i < MAXN; i++) {
 
        // If i is prime
        if (spf[i] == i) {
 
            // Marking SPF for all numbers divisible by i
            for (int j = i * i; j < MAXN; j += i)
 
                // Marking spf[j] if it is not
                // previously marked
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
// Function to return the sum of the elements of an array
// whose prime factors are present in the same array
int sumFactors(int arr[], int n)
{
 
    // Function call to calculate smallest prime factors of
    // all the numbers upto MAXN
    sieve();
 
    // Create map for each element
    std::map<int, int> map;
 
    for (int i = 0; i < n; ++i)
        map[arr[i]] = 1;
 
    int sum = 0;
 
    for (int i = 0; i < n; ++i) {
        int num = arr[i];
 
        // If smallest prime factor of num is present in array
        while (num != 1 && map[spf[num]] == 1) {
            num /= spf[num];
        }
 
        // Each factor of arr[i] is present in the array
        if (num == 1)
            sum += arr[i];
    }
 
    return sum;
}
 
// Driver program
int main()
{
    int arr[] = { 5, 11, 55, 25, 100 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to print required answer
    cout << sumFactors(arr, n);
    return 0;
}

// Java program to find the sum of the elements of an array
// whose prime factors are present in the same array
 
import java.util.*; 
 
public class GFG{
 
final static int MAXN = 1000001 ;
 
// Stores smallest prime factor for every number
static int spf[] = new int [MAXN];
 
    // Function to calculate SPF (Smallest Prime Factor)
    // for every number till MAXN
    static void sieve()
    {
        spf[1] = 1;
        for (int i = 2; i < MAXN; i++)
     
            // Marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;
     
        // Separately marking spf for every even
        // number as 2
        for (int i = 4; i < MAXN; i += 2)
            spf[i] = 2;
     
        for (int i = 3; i * i < MAXN; i++) {
     
            // If i is prime
            if (spf[i] == i) {
     
                // Marking SPF for all numbers divisible by i
                for (int j = i * i; j < MAXN; j += i)
     
                    // Marking spf[j] if it is not
                    // previously marked
                    if (spf[j] == j)
                        spf[j] = i;
            }
        }
    }
     
    // Function to return the sum of the elements of an array
    // whose prime factors are present in the same array
    static int sumFactors(int arr[], int n)
    {
     
        // Function call to calculate smallest prime factors of
        // all the numbers upto MAXN
        sieve();
     
        // Create map for each element
        Map map=new HashMap();
         
        for(int i = 0 ; i < MAXN ; ++i)
            map.put(i,0) ;
             
        for (int i = 0; i < n; ++i)
            map.put(arr[i],1);
         
     
        int sum = 0;
     
        for (int i = 0; i < n; ++i) {
            int num = arr[i];
     
            // If smallest prime factor of num is present in array
            while (num != 1 && (int)(map.get(spf[num])) == 1) {
                num /= spf[num];
            }
     
            // Each factor of arr[i] is present in the array
            if (num == 1)
                sum += arr[i];
        }
     
        return sum;
    }
     
    // Driver program
     public static void main(String []args)
    {
        int arr[] = { 5, 11, 55, 25, 100 };
        int n = arr.length ;
     
        // Function call to print required answer
         System.out.println(sumFactors(arr, n)) ;
    }
    // This code is contributed by Ryuga
}

# Python program to find the sum of the
# elements of an array whose prime factors
# are present in the same array
from collections import defaultdict
 
MAXN = 1000001
MAXN_sqrt = int(MAXN ** (0.5))
 
# Stores smallest prime factor
# for every number
spf = [None] * (MAXN)
 
# Function to calculate SPF (Smallest
# Prime Factor) for every number till MAXN
def sieve():
 
    spf[1] = 1
    for i in range(2, MAXN):
 
        # Marking smallest prime factor
        # for every number to be itself.
        spf[i] = i
 
    # Separately marking spf for every
    # even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2
 
    for i in range(3, MAXN_sqrt):
 
        # If i is prime
        if spf[i] == i:
 
            # Marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):
 
                # Marking spf[j] if it is 
                # not previously marked
                if spf[j] == j:
                    spf[j] = i
         
# Function to return the sum of the elements
# of an array whose prime factors are present
# in the same array
def sumFactors(arr, n):
 
    # Function call to calculate smallest
    # prime factors of all the numbers upto MAXN
    sieve()
 
    # Create map for each element
    Map = defaultdict(lambda:0)
 
    for i in range(0, n):
        Map[arr[i]] = 1
 
    Sum = 0
 
    for i in range(0, n):
        num = arr[i]
         
        # If smallest prime factor of num
        # is present in array
        while num != 1 and Map[spf[num]] == 1:
            num = num // spf[num]
         
        # Each factor of arr[i] is present
        # in the array
        if num == 1:
            Sum += arr[i]
     
    return Sum
 
# Driver Code
if __name__ == "__main__":
 
    arr = [5, 11, 55, 25, 100]
    n = len(arr)
 
    # Function call to print
    # required answer
    print(sumFactors(arr, n))
 
# This code is contributed by Rituraj Jain

// C# program to find the sum of the elements
// of an array whose prime factors are present
// in the same array
using System;
using System.Collections.Generic;
 
class GFG
{
    static int MAXN = 1000001;
     
    // Stores smallest prime factor for every number
    static int []spf = new int [MAXN];
 
    // Function to calculate SPF (Smallest Prime Factor)
    // for every number till MAXN
    static void sieve()
    {
        spf[1] = 1;
        for (int i = 2; i < MAXN; i++)
     
            // Marking smallest prime factor for
            // every number to be itself.
            spf[i] = i;
     
        // Separately marking spf for every even
        // number as 2
        for (int i = 4; i < MAXN; i += 2)
            spf[i] = 2;
     
        for (int i = 3; i * i < MAXN; i++)
        {
     
            // If i is prime
            if (spf[i] == i)
            {
     
                // Marking SPF for all numbers divisible by i
                for (int j = i * i; j < MAXN; j += i)
     
                    // Marking spf[j] if it is not
                    // previously marked
                    if (spf[j] == j)
                        spf[j] = i;
            }
        }
    }
     
    // Function to return the sum of the elements
    // of an array whose prime factors are present
    // in the same array
    static int sumFactors(int []arr, int n)
    {
     
        // Function call to calculate smallest
        // prime factors of all the numbers upto MAXN
        sieve();
     
        // Create map for each element
        Dictionary<int, int> map = new Dictionary<int, int>();
         
        for(int i = 0 ; i < MAXN ; ++i)
            map.Add(i, 0);
             
        for (int i = 0; i < n; ++i)
        {
            if(map.ContainsKey(arr[i]))
            {
                map[arr[i]] = 1;
            }
            else
            {
                map.Add(arr[i], 1);
            }
        }
         
        int sum = 0;
     
        for (int i = 0; i < n; ++i)
        {
            int num = arr[i];
     
            // If smallest prime factor of num
            // is present in array
            while (num != 1 &&
             (int)(map[spf[num]]) == 1)
            {
                num /= spf[num];
            }
     
            // Each factor of arr[i] is present
            // in the array
            if (num == 1)
                sum += arr[i];
        }
        return sum;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        int []arr = { 5, 11, 55, 25, 100 };
        int n = arr.Length;
     
        // Function call to print required answer
        Console.WriteLine(sumFactors(arr, n));
    }
}
 
// This code is contributed by PrinciRaj1992

96

Complejidad de tiempo: O(MAXN*log(log(MAXN)))

Espacio Auxiliar: O(MAXN)