Elementos de Array que se pueden expresar como potencia de números primos

Dada una array arr[] de tamaño N , la tarea es imprimir todos los elementos de la array que se pueden expresar como potencia de un número primo.

Ejemplos: 

Entrada: arr = {2, 8, 81, 36, 100} 
Salida: 2, 8, 81 
Explicación: 
Aquí 2 = 2 ¹ , 8 = 2 ³ y 81 = 3 ⁴

Entrada: arr = {4, 7, 144} 
Salida: 4, 7 
 

Acercarse:  

• La idea es usar la Criba de Eratóstenes y modificarla para almacenar todos los exponentes de los números primos en una array booleana. 
• Ahora recorra la array dada y para cada elemento verifique si está marcado como verdadero o no en la array booleana. 
• Si se marca como verdadero, imprime el número. 

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

// C++ program to print all elements
// of Array which can be expressed
// as power of prime numbers
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to mark all the
// exponent of prime numbers
void ModifiedSieveOfEratosthenes(
    int N, bool Expo_Prime[])
{
    bool primes[N];
    memset(primes, true, sizeof(primes));
 
    for (int i = 2; i < N; i++) {
 
        if (primes[i]) {
 
            int no = i;
 
            // If number is prime then marking
            // all of its exponent true
            while (no <= N) {
 
                Expo_Prime[no] = true;
                no *= i;
            }
 
            for (int j = i * i; j < N; j += i)
                primes[j] = false;
        }
    }
}
 
// Function to display all required elements
void Display(int arr[],
             bool Expo_Prime[],
             int n)
{
 
    for (int i = 0; i < n; i++)
        if (Expo_Prime[arr[i]])
            cout << arr[i] << " ";
}
 
// Function to print the required numbers
void FindExpoPrime(int arr[], int n)
{
    int max = 0;
 
    // To find the largest number
    for (int i = 0; i < n; i++) {
        if (max < arr[i])
            max = arr[i];
    }
 
    bool Expo_Prime[max + 1];
 
    memset(Expo_Prime, false,
           sizeof(Expo_Prime));
 
    // Function call to mark all the
    // Exponential prime nos.
    ModifiedSieveOfEratosthenes(
        max + 1, Expo_Prime);
 
    // Function call
    Display(arr, Expo_Prime, n);
}
 
// Driver code
int main()
{
    int arr[] = { 4, 6, 9, 16, 1, 3,
                  12, 36, 625, 1000 };
    int n = sizeof(arr) / sizeof(int);
 
    FindExpoPrime(arr, n);
 
    return 0;
}

// Java program to print all elements
// of Array which can be expressed
// as power of prime numbers
import java.util.*;
 
class GFG{
  
// Function to mark all the
// exponent of prime numbers
static void ModifiedSieveOfEratosthenes(
    int N, boolean Expo_Prime[])
{
    boolean []primes = new boolean[N];
    Arrays.fill(primes, true);
  
    for (int i = 2; i < N; i++) {
  
        if (primes[i]) {
  
            int no = i;
  
            // If number is prime then marking
            // all of its exponent true
            while (no <= N) {
  
                Expo_Prime[no] = true;
                no *= i;
            }
  
            for (int j = i * i; j < N; j += i)
                primes[j] = false;
        }
    }
}
  
// Function to display all required elements
static void Display(int arr[],
             boolean Expo_Prime[],
             int n)
{
  
    for (int i = 0; i < n; i++)
        if (Expo_Prime[arr[i]])
            System.out.print(arr[i]+ " ");
}
  
// Function to print the required numbers
static void FindExpoPrime(int arr[], int n)
{
    int max = 0;
  
    // To find the largest number
    for (int i = 0; i < n; i++) {
        if (max < arr[i])
            max = arr[i];
    }
  
    boolean []Expo_Prime = new boolean[max + 1];
 
  
    // Function call to mark all the
    // Exponential prime nos.
    ModifiedSieveOfEratosthenes(
        max + 1, Expo_Prime);
  
    // Function call
    Display(arr, Expo_Prime, n);
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 6, 9, 16, 1, 3,
                  12, 36, 625, 1000 };
    int n = arr.length;
  
    FindExpoPrime(arr, n);
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program to print all elements
# of Array which can be expressed
# as power of prime numbers
 
# Function to mark all the
# exponent of prime numbers
def ModifiedSieveOfEratosthenes(N, Expo_Prime) :
     
    primes = [True]*N;
 
    for i in range(2, N) :
        if (primes[i]) :
 
            no = i;
 
            # If number is prime then marking
            # all of its exponent true
            while (no <= N) :
 
                Expo_Prime[no] = True;
                no *= i;
 
            for j in range(i * i, N, i) :
                primes[j] = False;
     
# Function to display all required elements
def Display(arr, Expo_Prime, n) :
 
    for i in range(n) :
        if (Expo_Prime[arr[i]]) :
            print(arr[i], end= " ");
 
# Function to print the required numbers
def FindExpoPrime(arr, n) :
 
    max = 0;
 
    # To find the largest number
    for i in range(n) :
        if (max < arr[i]) :
            max = arr[i];
 
    Expo_Prime = [False]*(max + 1);
 
    # Function call to mark all the
    # Exponential prime nos.
    ModifiedSieveOfEratosthenes(max + 1, Expo_Prime);
 
    # Function call
    Display(arr, Expo_Prime, n);
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 4, 6, 9, 16, 1, 3,
                12, 36, 625, 1000 ];
    n = len(arr);
 
    FindExpoPrime(arr, n);
 
# This code is contributed by Yash_R

// C# program to print all elements
// of Array which can be expressed
// as power of prime numbers
using System;
 
class GFG{
 
// Function to mark all the
// exponent of prime numbers
static void ModifiedSieveOfEratosthenes(int N,
                            bool []Expo_Prime)
{
    bool []primes = new bool[N];
    for(int i = 0; i < N; i++)
        primes[i] = true;
         
    for(int i = 2; i < N; i++)
    {
       if (primes[i])
       {
           int no = i;
            
           // If number is prime then marking
           // all of its exponent true
           while (no <= N)
           {
               Expo_Prime[no] = true;
               no *= i;
           }
           for(int j = i * i; j < N; j += i)
              primes[j] = false;
       }
    }
}
 
// Function to display all required
// elements
static void Display(int []arr,
                    bool []Expo_Prime,
                    int n)
{
    for(int i = 0; i < n; i++)
       if (Expo_Prime[arr[i]])
           Console.Write(arr[i] + " ");
}
 
// Function to print the required numbers
static void FindExpoPrime(int []arr, int n)
{
    int max = 0;
 
    // To find the largest number
    for(int i = 0; i < n; i++)
    {
       if (max < arr[i])
           max = arr[i];
    }
 
    bool []Expo_Prime = new bool[max + 1];
 
    // Function call to mark all the
    // Exponential prime nos.
    ModifiedSieveOfEratosthenes(max + 1,
                                Expo_Prime);
                                 
    // Function call
    Display(arr, Expo_Prime, n);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 4, 6, 9, 16, 1, 3,
                  12, 36, 625, 1000 };
    int n = arr.Length;
 
    FindExpoPrime(arr, n);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to print all elements
// of Array which can be expressed
// as power of prime numbers
 
 
// Function to mark all the
// exponent of prime numbers
function ModifiedSieveOfEratosthenes(N, Expo_Prime)
{
    let primes = new Array(N);
    primes.fill(true)
 
    for (let i = 2; i < N; i++) {
 
        if (primes[i]) {
 
            let no = i;
 
            // If number is prime then marking
            // all of its exponent true
            while (no <= N) {
 
                Expo_Prime[no] = true;
                no *= i;
            }
 
            for (let j = i * i; j < N; j += i)
                primes[j] = false;
        }
    }
}
 
// Function to display all required elements
function Display(arr, Expo_Prime, n)
{
 
    for (let i = 0; i < n; i++)
        if (Expo_Prime[arr[i]])
            document.write(arr[i] + " ");
}
 
// Function to print the required numbers
function FindExpoPrime(arr, n)
{
    let max = 0;
 
    // To find the largest number
    for (let i = 0; i < n; i++) {
        if (max < arr[i])
            max = arr[i];
    }
 
    let Expo_Prime = new Array(max + 1);
    Expo_Prime.fill(false)
 
    // Function call to mark all the
    // Exponential prime nos.
    ModifiedSieveOfEratosthenes(
        max + 1, Expo_Prime);
 
    // Function call
    Display(arr, Expo_Prime, n);
}
 
// Driver code
 
    let arr = [ 4, 6, 9, 16, 1, 3,
                12, 36, 625, 1000 ];
    let n = arr.length
 
    FindExpoPrime(arr, n);
 
// This code is contributed by gfgking
 
</script>

4 9 16 3 625

Complejidad de tiempo: O(N*log(log(N))), donde N representa el elemento máximo en la array.
Espacio Auxiliar: O(N), donde N representa el elemento máximo en el arreglo.