Python Program to Reverse all Prime Numbers in Array Without Affecting Elements
Given an array, our task is to Reverse all prime numbers in an array without affecting other elements in Python.
Examples:
Input : arr = {1, 2, 3, 4, 5, 6} Output : {1,5,3,4,2,6} Explanation: Prime elements in given array are 2,3,5. After reversing the modified array will be {1,5,3,4,2,6}
Approach:
- Start traversing the array from left to right.
- Maintain another array for storing prime numbers.
- If the current element is prime then append the current element to the prime array.
- Start traversing the array again and replace the prime element with the element present in the prime array from the last.
- Finally, return the modified array.
Below is the implementation of the above approach
Python3
from math import sqrt # Function to check element is prime def isPrime(x): # flag maintains status if x is prime prime = 0 if (x > 1 ): for i in range ( 2 , int (sqrt(x)) + 1 ): if (x % i = = 0 ): prime = 1 break if (prime = = 0 ): return True else : return False else : return False def reversePrimes(arr): n = len (arr) # array to store prime elements prime = [] for i in range (n): if isPrime(arr[i]): prime.append(arr[i]) # variable to store index of prime array k = len (prime) - 1 # Traversing again to modify the array for i in range (n): if isPrime(arr[i]): arr[i] = prime[k] k = k - 1 return arr print (reversePrimes([ 1 , 2 , 3 , 4 , 5 , 6 ])) |
[1, 5, 3, 4, 2, 6]
Complexity Analysis:
Let x be the largest prime number in the array.
Time complexity: O(n*sqrt(x))
Space Complexity: O(n) for storing prime elements
METHOD 2: Using a sieve method.
APPROACH:
The “reverse_primes_4” function takes an input array “arr” and returns a new array with all the prime numbers in “arr” reversed while keeping the non-prime numbers in their original position. It uses a sieve of Eratosthenes algorithm to generate a list of primes up to the maximum value in “arr”, and then reverses this list. It then iterates through “arr”, swaps any prime numbers it finds with the first prime in the reversed list, and removes that prime from the reversed list.
ALGORITHM:
1. Use a sieve to generate a list of primes up to the maximum element in the input array.
2. Reverse the list of primes.
3. Loop through the input array and swap any prime elements with the corresponding element from the reversed list of primes.
4. Return the modified input array.
Python3
def reverse_primes_4(arr): # create a list of primes using a sieve n = max (arr) sieve = [ True ] * (n + 1 ) sieve[ 0 ] = sieve[ 1 ] = False for i in range ( 2 , int (n * * 0.5 ) + 1 ): if sieve[i]: for j in range (i * * 2 , n + 1 , i): sieve[j] = False primes = [i for i in range ( 2 , n + 1 ) if sieve[i]] # reverse the primes and create a new list with the swapped elements primes.reverse() new_arr = [] for i in arr: if i in primes: new_arr.append(primes.pop( 0 )) else : new_arr.append(i) return new_arr # example usage: arr = [ 1 , 2 , 3 , 4 , 2 , 6 ] result = reverse_primes_4(arr) print (result) # output: [1, 5, 3, 4, 2, 6] |
[1, 5, 3, 4, 2, 6]
Time complexity: O(n*log(log(n))), where n is the maximum element in the input array (due to the time complexity of the sieve algorithm)
Space complexity: O(n)