Given an array arr[] of size N, the task is to print all the elements of the Array which can be expressed as power of a prime number.
Examples:
Input: arr = {2, 8, 81, 36, 100}
Output: 2, 8, 81
Explanation:
Here 2 = 21, 8 = 23 and 81 = 34Input: arr = {4, 7, 144}
Output: 4, 7
Naive approach:
In the approach we checks for each element of the array whether it can be expressed as a power of a prime number. It does this by looping through each prime number less than or equal to the square root of the element, and then checking whether the element can be expressed as the power of the prime number. This approach tries all possible prime numbers and powers until a match is found,it may consume more time for large input array.
Explanation:
1. The is_prime function is used to check whether a given number is prime or not.
2. For each element, the function loops through all the prime numbers less than or equal to the square root of the element.
3. For each prime number, the function checks whether the element can be expressed as the power of the prime number. If it can, then the element is printed and the loop is exited.
4. If the loop completes without finding any prime number that can express the element as its power, then the function checks whether the element itself is prime. If it is, then it is printed.
5. Finally, the main function initializes the input array and its size and calls the print_power_primes function to print the elements that can be expressed as the power of a prime number.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;bool is_prime(int num) { if (num <= 1) { return false; } for (int i = 2; i <= sqrt(num); i++) { if (num % i == 0) { return false; } } return true;}void print_powerprimes(int arr[], int n) { for (int i = 0; i < n; i++) { int num = arr[i]; bool is_power_prime = false; for (int j = 2; j <= sqrt(num); j++) { if (is_prime(j) && num == pow(j, round(log(num) / log(j)))) { cout << num << " "; is_power_prime = true; break; } } if (!is_power_prime && is_prime(num)) { cout << num << " "; } }}int main() { int arr[] = {2, 8, 81, 36, 100}; int n = sizeof(arr) / sizeof(arr[0]); print_powerprimes(arr, n); return 0;} |
Java
import java.util.Arrays;class GFG { // Function to check if a number is prime static boolean isPrime(int num) { if (num <= 1) { return false; } for (int i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) { return false; } } return true; } // Function to print power primes in the array static void printPowerPrimes(int[] arr) { for (int num : arr) { boolean isPowerPrime = false; for (int j = 2; j <= Math.sqrt(num); j++) { // Check if 'j' is prime and num is a power of 'j' if (isPrime(j) && num == Math.pow(j, Math.round(Math.log(num) / Math.log(j)))) { System.out.print(num + " "); isPowerPrime = true; break; } } // Check if num is prime if (!isPowerPrime && isPrime(num)) { System.out.print(num + " "); } } } public static void main(String[] args) { int[] arr = {2, 8, 81, 36, 100}; printPowerPrimes(arr); // This Code Is Contributed By Shubham Tiwari. }} |
Python3
import mathdef is_prime(num): if num <= 1: return False for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: return False return Truedef print_powerprimes(arr): for num in arr: is_power_prime = False for j in range(2, int(math.sqrt(num)) + 1): if is_prime(j) and num == pow(j, round(math.log(num) / math.log(j))): print(num, end=" ") is_power_prime = True break if not is_power_prime and is_prime(num): print(num, end=" ")if __name__ == "__main__": arr = [2, 8, 81, 36, 100] print_powerprimes(arr) # This code is Contributed By Shubham Tiwari. |
C#
using System;class GFG{ static bool IsPrime(int num) { if (num <= 1) { return false; } for (int i = 2; i <= Math.Sqrt(num); i++) { if (num % i == 0) { return false; } } return true; } static void PrintPowerPrimes(int[] arr) { for (int i = 0; i < arr.Length; i++) { int num = arr[i]; bool isPowerPrime = false; for (int j = 2; j <= Math.Sqrt(num); j++) { if (IsPrime(j) && num == Math.Pow(j, Math.Round(Math.Log(num) / Math.Log(j)))) { Console.Write(num + " "); isPowerPrime = true; break; } } if (!isPowerPrime && IsPrime(num)) { Console.Write(num + " "); } } } //Drive Code static void Main(string[] args) { int[] arr = { 2, 8, 81, 36, 100 }; PrintPowerPrimes(arr); // This code is contributed by Shubham Tiwari. }} |
Javascript
// Function to check if a number is primefunction is_prime(num) { if (num <= 1) { return false; } for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { return false; } } return true;}// Function to print power primes in the arrayfunction print_powerprimes(arr) { for (let i = 0; i < arr.length; i++) { let num = arr[i]; let is_power_prime = false; for (let j = 2; j <= Math.sqrt(num); j++) { // Check if 'j' is prime and num is a power of 'j' if (is_prime(j) && num === Math.pow(j, Math.round(Math.log(num) / Math.log(j)))) { console.log(num + " "); is_power_prime = true; break; } } // Check if num is prime if (!is_power_prime && is_prime(num)) { console.log(num + " "); } }}const arr = [2, 8, 81, 36, 100];print_powerprimes(arr);// This Code Is Contributed By Shubham Tiwari. |
Output
2 8 81
Time Complexity: O(N^2), where N represents the maximum element in the array.
Auxiliary Space: O(N), where N represents the maximum element in the array.
Approach:
- The idea is to use Sieve of Eratosthenes and modify it to store all the exponent of prime numbers in a boolean array.
- Now traverse the given array and for each element check whether it is marked true or not in the boolean array.
- If marked true, Print the number.
Below is the implementation of the above approach:
C++
// 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 numbersvoid 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 elementsvoid 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 numbersvoid 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 codeint 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
// Java program to print all elements// of Array which can be expressed// as power of prime numbersimport java.util.*;class GFG{ // Function to mark all the// exponent of prime numbersstatic 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 elementsstatic 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 numbersstatic 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 codepublic 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
# 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#
// C# program to print all elements// of Array which can be expressed// as power of prime numbersusing System;class GFG{// Function to mark all the// exponent of prime numbersstatic 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// elementsstatic 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 numbersstatic 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 codepublic 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 |
Javascript
<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 numbersfunction 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 elementsfunction 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 numbersfunction 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> |
Output
4 9 16 3 625
Time Complexity: O(N*log(log(N))), where N represents the maximum element in the array.
Auxiliary Space: O(N), where N represents the maximum element in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
