Dada una array arr[] que contiene números primos y no primos repetitivos, la tarea es encontrar los números primos que ocurren solo una vez.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 6, 7, 9, 7, 23, 21, 2, 3}
Salida: 23
Explicación:
En la array dada, 23 es el único número primo que aparece una vez.Entrada: arr[] = {17, 19, 7, 5, 29, 5, 2, 2, 7, 17, 19}
Salida: 29
Explicación:
En la array dada, 29 es el único número primo que aparece una vez.
Enfoque ingenuo: para resolver el problema mencionado anteriormente, la solución es verificar cada elemento si es primo. Si es principal, compruebe si aparece solo una vez o no. Una vez que se encuentra un elemento primo con una sola ocurrencia, imprímalo.
Complejidad temporal: O(N 2 )
Enfoque eficiente: el enfoque anterior se puede optimizar aún más utilizando el algoritmo Sieve y Hashing .
- Precalcule y almacene números primos usando Sieve en una tabla hash .
- También cree un HashMap para almacenar los números con su frecuencia.
- Recorra todos los elementos de la array uno por uno y:
- Verifique si el número actual es primo o no, usando la Tabla hash de criba en O(1).
- Si el número es primo, aumente su frecuencia en HashMap.
- Recorra el HashMap e imprima todos los números que tienen la frecuencia 1.
A continuación se muestra la implementación del enfoque anterior:
Java
// 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
# 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#
// 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
Javascript
<script>
// JavaScript program to find
// Non-repeating Primes
// Function to find count of prime
function findPrimes(arr, n){
// Find maximum value in the array
let max_val = Math.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.
let prime = new Array(max_val + 1).fill(true);
// Remaining part of SIEVE
prime[0] = false
prime[1] = false
let 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(let i = p * 2; i< max_val + 1; i += p)
prime[i] = false
}
p += 1
}
return prime
}
// Function to print
// Non-repeating primes
function nonRepeatingPrimes(arr, n){
// Precompute primes using Sieve
let prime = findPrimes(arr, n);
// Create HashMap to store
// frequency of prime numbers
let mp = new Map();
// Traverse through array elements and
// Count frequencies of all primes
for(let i=0;i<n;i++){
if (prime[arr[i]]){
if (mp.has(arr[i]))
mp.set(arr[i], mp.get(arr[i])+1)
else
mp.set(arr[i],1)
}
}
// Traverse through map and
// print non repeating primes
for(let [key,value] of mp){
if (value == 1)
document.write(key,"</br>");
}
}
// Driver code
let arr = [2, 3, 4, 6, 7, 9, 7, 23, 21, 3]
let n = arr.length
nonRepeatingPrimes(arr, n)
// This code is contributed by shinjanpatra
</script>
Producción:
2 23
Complejidad de tiempo: O(O(n*log(log(n))))
Espacio auxiliar: O(K), donde K es el valor más grande de la array.
Publicación traducida automáticamente
Artículo escrito por master_abhig y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA