Given an array arr[] containing repetitive prime and nonprime numbers, the task is to find the prime numbers occurring only once.
Examples:
Input: arr[] = {2, 3, 4, 6, 7, 9, 7, 23, 21, 2, 3}
Output: 23
Explanation:
In the given array, 23 is the only prime number which appears once.Input: arr[] = {17, 19, 7, 5, 29, 5, 2, 2, 7, 17, 19}
Output: 29
Explanation:
In the given array, 29 is the only prime number which appears once.
Naive Approach: To solve the problem mentioned above the solution is to check every element if it is prime. If it is prime, then check is it appears only once or not. Once a prime element with a single occurrence is found, print it.
Time complexity: O(N2)
Efficient Approach: The above approach can be further optimised using Sieve and Hashing algorithm.
- Precompute and store prime numbers using Sieve in a Hash Table.
- Also create a HashMap to store the numbers with their frequency.
- Traverse all elements in the array one by one and:
- Check if the current number is prime or not, using the Sieve Hash Table in O(1).
- If the number is prime, then increase its frequency in the HashMap.
- Traverse the HashMap, and print all the numbers which have the frequency 1.
Below is the implementation of the above approach:
C++
// C++ program to find // Non-repeating Primes #include <bits/stdc++.h> using namespace std; // Function to find count of prime vector< bool > findPrimes( int arr[], int n) { // Find maximum value in the array int max_val = *max_element(arr, arr + n); // 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< bool > prime(max_val + 1, 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 void nonRepeatingPrimes( int arr[], int n) { // Precompute primes using Sieve vector< bool > prime = findPrimes(arr, n); // Create HashMap to store // frequency of prime numbers map< int , int > mp ; // Traverse through array elements and // Count frequencies of all primes for ( int i = 0; i < n; i++) { if (prime[arr[i]]) mp[arr[i]]++; } // Traverse through map and // print non repeating primes for ( auto entry : mp) { if (entry.second == 1) cout << entry.first << endl; } } // Driver code int main() { int arr[] = { 2, 3, 4, 6, 7, 9, 7, 23, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); nonRepeatingPrimes(arr, n); } // This code is contributed by phasing17 |
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> |
2 23
Time complexity: O(O(n*log(log(n))))
Auxiliary Space: O(K), where K is the largest value in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!