Dado um array arr [] contendo números primos e não-primos repetitivos, a tarefa é encontrar os números primos ocorrendo apenas uma vez.

Exemplos: 

Entrada: arr [] = {2, 3, 4, 6, 7, 9, 7, 23, 21, 2, 3} 
Saída: 23 
Explicação: 
Na array fornecida, 23 é o único número primo que aparece uma vez.

Entrada: arr [] = {17, 19, 7, 5, 29, 5, 2, 2, 7, 17, 19} 
Saída: 29 
Explicação: 
Na array fornecida, 29 é o único número primo que aparece uma vez. 

Abordagem ingênua: Para resolver o problema mencionado acima, a solução é verificar se cada elemento é primo. Se for primo, verifique se aparece apenas uma vez ou não. Quando um elemento primo com uma única ocorrência for encontrado, imprima-o.

Complexidade de tempo: O (N ² )

Abordagem eficiente: A abordagem acima pode ser otimizada ainda mais usando o algoritmo Sieve e Hashing . 

1. Pré-calcule e armazene os números primos usando o Sieve in a Hash Table .
2. Crie também um HashMap para armazenar os números com sua frequência.
3. Percorra todos os elementos da array um por um e: 
   • Verifique se o número atual é primo ou não, usando a tabela de hash da peneira em O (1).
   • Se o número for primo, aumente sua frequência no HashMap.
4. Percorra o HashMap e imprima todos os números que possuem a frequência 1.

Abaixo está a implementação da abordagem acima: 

// Java program to find
// Non-repeating Primes
 
import java.util.*;
 
class GFG {
 
    // Function to find count of prime
    static Vector<Boolean> findPrimes(
        int arr[], int n)
    {
        // Find maximum value in the array
        int max_val = Arrays
                          .stream(arr)
                          .max()
                          .getAsInt();
 
        // Find and store all prime numbers
        // up to max_val using Sieve
 
        // 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<>(max_val + 1);
 
        for (int i = 0; i < max_val + 1; i++)
            prime.add(i, Boolean.TRUE);
 
        // Remaining part of SIEVE
        prime.add(0, Boolean.FALSE);
        prime.add(1, Boolean.FALSE);
        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);
            }
        }
 
        return prime;
    }
 
    // Function to print
    // Non-repeating primes
    static void nonRepeatingPrimes(
        int arr[], int n)
    {
 
        // Precompute primes using Sieve
        Vector<Boolean> prime
            = findPrimes(arr, n);
 
        // Create HashMap to store
        // frequency of prime numbers
        HashMap<Integer, Integer> mp
            = new HashMap<>();
 
        // Traverse through array elements and
        // Count frequencies of all primes
        for (int i = 0; i < n; i++) {
            if (prime.get(arr[i]))
                if (mp.containsKey(arr[i]))
                    mp.put(arr[i],
                           mp.get(arr[i]) + 1);
                else
                    mp.put(arr[i], 1);
        }
 
        // Traverse through map and
        // print non repeating primes
        for (Map.Entry<Integer, Integer>
                 entry : mp.entrySet()) {
            if (entry.getValue() == 1)
                System.out.println(
                    entry.getKey());
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 3, 4, 6, 7, 9,
                      7, 23, 21, 3 };
        int n = arr.length;
 
        nonRepeatingPrimes(arr, n);
    }
}

# Python3 program to find
# Non-repeating Primes
 
# Function to find count of prime
def findPrimes( arr, n):
 
    # Find maximum value in the array
    max_val =  max(arr)
     
    # Find and store all prime numbers
    # up to max_val using Sieve
    # 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
    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     
    return prime;
 
# Function to print
# Non-repeating primes
def nonRepeatingPrimes(arr, n):
 
    # Precompute primes using Sieve
    prime = findPrimes(arr, n);
     
    # Create HashMap to store
    # frequency of prime numbers
    mp = dict()
 
    # Traverse through array elements and
    # Count frequencies of all primes
    for i in range(n):  
        if (prime[arr[i]]):
            if (arr[i] in mp):
                mp[arr[i]] += 1
            else:
                mp[arr[i]] = 1
     
    # Traverse through map and
    # print non repeating primes
    for entry in mp.keys():
        if (mp[entry] == 1):
            print(entry);
     
# Driver code
if __name__ == '__main__':
    arr = [ 2, 3, 4, 6, 7, 9, 7, 23, 21, 3]
    n = len(arr)
    nonRepeatingPrimes(arr, n);
 
# This code is contributed by pratham76.

// C# program to find
// Non-repeating Primes
using System;
using System.Collections;
using System.Linq;
using System.Collections.Generic;
 
class GFG{
 
// Function to find count of prime
static List<bool> findPrimes(int []arr, int n)
{
     
    // Find maximum value in the array
    int max_val = arr.Max();
 
    // Find and store all prime numbers
    // up to max_val using Sieve
 
    // 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<bool> prime = new List<bool>(max_val + 1);
 
    for(int i = 0; i < max_val + 1; i++)
        prime.Add(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;
        }
    }
    return prime;
}
 
// Function to print
// Non-repeating primes
static void nonRepeatingPrimes(int []arr, int n)
{
     
    // Precompute primes using Sieve
    List<bool> prime = findPrimes(arr, n);
 
    // Create HashMap to store
    // frequency of prime numbers
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
 
    // Traverse through array elements and
    // Count frequencies of all primes
    for(int i = 0; i < n; i++)
    {
        if (prime[arr[i]])
            if (mp.ContainsKey(arr[i]))
                mp[arr[i]]++;
            else
                mp.Add(arr[i], 1);
    }
 
    // Traverse through map and
    // print non repeating primes
    foreach(KeyValuePair<int, int> entry in mp)
    {
        if (entry.Value == 1)
            Console.WriteLine(entry.Key);
    }
}
 
// Driver code
public static void Main(string[] args)
{
    int []arr = { 2, 3, 4, 6, 7, 9,
                  7, 23, 21, 3 };
    int n = arr.Length;
 
    nonRepeatingPrimes(arr, n);
}
}
 
// This code is contributed by rutvik_56

2
23

Complexidade de tempo: O (O (n * log (log (n)))) 
Espaço auxiliar: O (K), onde K é o maior valor na array.