Cuente factores primos distintos para cada elemento de una array

Dada una array arr[] de tamaño N , la tarea es encontrar el recuento de distintos factores primos de cada elemento de la array dada.

Ejemplos:

Entrada: arr[] = {6, 9, 12}
Salida: 2 1 2
Explicación:

• 6 = 2 × 3 . Por lo tanto, cuenta = 2
• 9 = 3 × 3. Por lo tanto, cuenta = 1
• 12 = 2 × 2 × 3 . Por lo tanto, cuenta = 2

El recuento de factores primos distintos de cada elemento de la array es 2, 1, 2 respectivamente.

Entrada: arr[] = {4, 8, 10, 6}
Salida : 1 1 2 2

Enfoque ingenuo: el enfoque más simple para resolver el problema es encontrar los factores primos de cada elemento de la array. Luego, encuentre los distintos números primos entre ellos e imprima ese recuento para cada elemento de la array. 
Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar calculando previamente los distintos factores de todos los números utilizando sus factores primos más pequeños . Siga los pasos a continuación para resolver el problema

• Inicialice un vector , digamos v , para almacenar los distintos factores primos.
• Almacene el factor primo más pequeño (SPF) hasta 10 ⁵ utilizando un tamiz de Eratóstenes .
• Calcule los distintos factores primos de todos los números dividiendo recursivamente los números con su factor primo más pequeño hasta que se reduzca a 1 y almacene distintos factores primos de X , en v[X] .
• Recorra la array arr[] y para cada elemento de la array, imprima el conteo como v[arr[i]].size() .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
 
// Stores smallest prime
// factor for every number
int spf[MAX];
 
// Stores distinct prime factors
vector<int> v[MAX];
 
// Function to find the smallest
// prime factor of every number
void sieve()
{
    // Mark the smallest prime factor
    // of every number to itself
    for (int i = 1; i < MAX; i++)
        spf[i] = i;
 
    // Separately mark all the
    // smallest prime factor of
    // every even number to be 2
    for (int i = 4; i < MAX; i = i + 2)
        spf[i] = 2;
 
    for (int i = 3; i * i < MAX; i++)
 
        // If i is prime
        if (spf[i] == i) {
 
            // Mark spf for all numbers
            // divisible by i
            for (int j = i * i; j < MAX;
                 j = j + i) {
 
                // Mark spf[j] if it is
                // not previously marked
                if (spf[j] == j)
                    spf[j] = i;
            }
        }
}
 
// Function to find the distinct
// prime factors
void DistPrime()
{
    for (int i = 1; i < MAX; i++) {
 
        int idx = 1;
        int x = i;
 
        // Push all distinct of x
        // prime factor in v[x]
        if (x != 1)
            v[i].push_back(spf[x]);
 
        x = x / spf[x];
 
        while (x != 1) {
 
            if (v[i][idx - 1]
                != spf[x]) {
 
                // Pushback into v[i]
                v[i].push_back(spf[x]);
 
                // Increment the idx
                idx += 1;
            }
 
            // Update x = (x / spf[x])
            x = x / spf[x];
        }
    }
}
 
// Function to get the distinct
// factor count of arr[]
void getFactorCount(int arr[],
                    int N)
{
    // Precompute the smallest
    // Prime Factors
    sieve();
 
    // For distinct prime factors
    // Fill the v[] vector
    DistPrime();
 
    // Count of Distinct Prime
    // Factors of each array element
    for (int i = 0; i < N; i++) {
        cout << (int)v[arr[i]].size()
             << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 9, 12 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    getFactorCount(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
 
  static int MAX = 100001;
 
  // Stores smallest prime
  // factor for every number
  static int spf[];
 
  // Stores distinct prime factors
  static ArrayList<Integer> v[];
 
  // Function to find the smallest
  // prime factor of every number
  static void sieve()
  {
 
    // Mark the smallest prime factor
    // of every number to itself
    for (int i = 1; i < MAX; i++)
      spf[i] = i;
 
    // Separately mark all the
    // smallest prime factor of
    // every even number to be 2
    for (int i = 4; i < MAX; i = i + 2)
      spf[i] = 2;
    for (int i = 3; i * i < MAX; i++)
 
      // If i is prime
      if (spf[i] == i) {
 
        // Mark spf for all numbers
        // divisible by i
        for (int j = i * i; j < MAX; j = j + i) {
 
          // Mark spf[j] if it is
          // not previously marked
          if (spf[j] == j)
            spf[j] = i;
        }
      }
  }
 
  // Function to find the distinct
  // prime factors
  static void DistPrime()
  {
    for (int i = 1; i < MAX; i++) {
 
      int idx = 1;
      int x = i;
 
      // Push all distinct of x
      // prime factor in v[x]
      if (x != 1)
        v[i].add(spf[x]);
 
      x = x / spf[x];
 
      while (x != 1) {
 
        if (v[i].get(idx - 1) != spf[x]) {
 
          // Pushback into v[i]
          v[i].add(spf[x]);
 
          // Increment the idx
          idx += 1;
        }
 
        // Update x = (x / spf[x])
        x = x / spf[x];
      }
    }
  }
 
  // Function to get the distinct
  // factor count of arr[]
  static void getFactorCount(int arr[], int N)
  {
 
    // initialization
    spf = new int[MAX];
    v = new ArrayList[MAX];
    for (int i = 0; i < MAX; i++)
      v[i] = new ArrayList<>();
 
    // Precompute the smallest
    // Prime Factors
    sieve();
 
    // For distinct prime factors
    // Fill the v[] vector
    DistPrime();
 
    // Count of Distinct Prime
    // Factors of each array element
    for (int i = 0; i < N; i++) {
      System.out.print((int)v[arr[i]].size() + " ");
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    int arr[] = { 6, 9, 12 };
    int N = arr.length;
 
    getFactorCount(arr, N);
  }
}
 
// This code is contributed by Kingash.

<script>
 
    // JavaScript program for the above approach
     
    let MAX = 100001;
  
    // Stores smallest prime
    // factor for every number
    let spf;
 
    // Stores distinct prime factors
    let v;
 
    // Function to find the smallest
    // prime factor of every number
    function sieve()
    {
 
      // Mark the smallest prime factor
      // of every number to itself
      for (let i = 1; i < MAX; i++)
        spf[i] = i;
 
      // Separately mark all the
      // smallest prime factor of
      // every even number to be 2
      for (let i = 4; i < MAX; i = i + 2)
        spf[i] = 2;
      for (let i = 3; i * i < MAX; i++)
 
        // If i is prime
        if (spf[i] == i) {
 
          // Mark spf for all numbers
          // divisible by i
          for (let j = i * i; j < MAX; j = j + i) {
 
            // Mark spf[j] if it is
            // not previously marked
            if (spf[j] == j)
              spf[j] = i;
          }
        }
    }
 
    // Function to find the distinct
    // prime factors
    function DistPrime()
    {
      for (let i = 1; i < MAX; i++) {
 
        let idx = 1;
        let x = i;
 
        // Push all distinct of x
        // prime factor in v[x]
        if (x != 1)
          v[i].push(spf[x]);
 
        x = parseInt(x / spf[x], 10);
 
        while (x != 1) {
 
          if (v[i][idx - 1] != spf[x]) {
 
            // Pushback into v[i]
            v[i].push(spf[x]);
 
            // Increment the idx
            idx += 1;
          }
 
          // Update x = (x / spf[x])
          x = parseInt(x / spf[x], 10);
        }
      }
    }
 
    // Function to get the distinct
    // factor count of arr[]
    function getFactorCount(arr, N)
    {
 
      // initialization
      spf = new Array(MAX);
      v = new Array(MAX);
      for (let i = 0; i < MAX; i++)
        v[i] = [];
 
      // Precompute the smallest
      // Prime Factors
      sieve();
 
      // For distinct prime factors
      // Fill the v[] vector
      DistPrime();
 
      // Count of Distinct Prime
      // Factors of each array element
      for (let i = 0; i < N; i++) {
        document.write(v[arr[i]].length + " ");
      }
    }
     
    let arr = [ 6, 9, 12 ];
    let N = arr.length;
  
    getFactorCount(arr, N);
   
</script>

2 1 2

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)