Check prime numbers in Array against prime index positions
Given an array arr[], the task is to check for each prime number in the array, from its position(indexing from 1) to each non-prime position index, and check if the number present in that position is prime or not.
Examples:
Input: arr[] = {5, 9, 3, 7, 8, 2}
Output: Prime
Explanation:
- First prime number found is 5. For 5, two non-prime positions are 4 and 6 whose values are 7 and 2 respectively, and both of them are prime numbers.
- Next prime number found is 3. For 3, only one non-prime position is 4 whose value is 2, and it is a prime number.
- Next prime number found is 7. For 7, there are not any prime positions within a range of the array, so we skip it.
- Next prime number found is 2. For 2, there are not any prime positions within the range of the array, so we skip it.
Input: arr[] = {5, 3, 7, 8, 11}
Output: Not Prime
Explanation: The first prime number found is 5. For 5, only one non-prime position is 4 whose value is 8, and it is not a prime number. So, the answer will be Not Prime and we don’t check the other prime numbers.
Approach: This can be solved with the following idea:
- First, we need to check for the prime numbers inside the array.
- For each prime number,
- We check if all of the elements of its corresponding non-prime indexes (indexing from 1) are prime or not.
- If both the conditions satisfy, then we print Prime otherwise Non-Prime.
Below are the steps of the code:
- Define a function called “is_prime” that takes a non-negative integer “n” as input and returns a Boolean value (True or False) depending on whether “n” is prime or not.
- In the “is_prime” function, first, check if “n” is less than or equal to 1. If it is, then return False.
- If “n” is 2 or 3, then return True.
- Check whether “n” is divisible by 2 or 3. If it is, then return False.
- Iterate from 5 to the square root of “n” with a step size of 6 and check if “n” is divisible by any of these numbers or the number obtained by adding 2 to each of these numbers.
- If “n” is divisible by any of these numbers, then return False.
- Otherwise, return True.
- Define another function called “check” that takes an array “arr” and its length “n” as input and returns a Boolean value (True or False) depending on whether the given array is a “Prime” array or a
“Non-Prime” array.- In the “check” function, first store all possible non-prime indexes in an array/list called “non_prime_numbers” by iterating over the range 2 to (n+1) and checking if each number is not prime using the “is_prime” function.
- Get the length of the “non_prime_numbers” list and iterate over the range (n) using a for a loop.
- Check if the current element of the array is a prime number or not using the “is_prime” function.
- If it is not a prime number, then continue to the next iteration.
- If the current element is a prime number, check if the lowest value of the non-prime number is out of range for the current index. If it is, then break out of the for loop.
- If the lowest value of the non-prime number is within range, iterate over the “non_prime_numbers” list using a while loop and check if each index of the array obtained by adding the corresponding non-prime number and subtracting 1 from the current index is a prime number or not using the “is_prime” function.
- If any of these indexes is not a prime number, then return False.
- Otherwise, continue to the next iteration.
- If all the conditions are dissatisfied, then return True from the “check” function.
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a number is prime bool is_prime( int n) { if (n <= 1) { return false ; } if (n == 2 || n == 3) { return true ; } if (n % 2 == 0 || n % 3 == 0) { return false ; } // Check divisibility by numbers of the form 6k ± 1 for ( int i = 5; i <= sqrt (n); i += 6) { if (n % i == 0 || n % (i + 2) == 0) { return false ; } } return true ; } // Function to check if the given array satisfies the // conditions bool check(vector< int >& arr, int n) { vector< int > non_prime_numbers; // Find all non-prime numbers in the range [2, n] for ( int i = 2; i <= n; i++) { if (!is_prime(i)) { non_prime_numbers.push_back(i); } } int np = non_prime_numbers.size(); // Iterate over the array elements for ( int i = 0; i < n; i++) { if (is_prime(arr[i])) { // If the current element is prime, check the // subsequent non-prime positions if ((i + 3) >= n) { break ; } int j = 0; while (j < np && (i + non_prime_numbers[j] - 1) < n) { // Check if the number in the non-prime // position is not prime if (!is_prime(arr[i + non_prime_numbers[j] - 1])) { return false ; } j++; } } } return true ; } // Driver code int main() { vector< int > arr = { 5, 9, 3, 7, 8, 2 }; int n = arr.size(); // Function call if (check(arr, n)) { cout << "Prime" << endl; } else { cout << "Non Prime" << endl; } return 0; } // This code is contributed by rambabuguphka |
Java
// Java code for the above approach import java.util.ArrayList; import java.util.List; public class GFG { // Function to check if a number is prime static boolean isPrime( int n) { if (n <= 1 ) { return false ; } if (n == 2 || n == 3 ) { return true ; } if (n % 2 == 0 || n % 3 == 0 ) { return false ; } // Check divisibility by numbers of the form 6k ± 1 for ( int i = 5 ; i <= Math.sqrt(n); i += 6 ) { if (n % i == 0 || n % (i + 2 ) == 0 ) { return false ; } } return true ; } // Function to check if the given array satisfies the // conditions static boolean check(List<Integer> arr, int n) { List<Integer> nonPrimeNumbers = new ArrayList<>(); // Find all non-prime numbers in the range [2, n] for ( int i = 2 ; i <= n; i++) { if (!isPrime(i)) { nonPrimeNumbers.add(i); } } int np = nonPrimeNumbers.size(); // Iterate over the array elements for ( int i = 0 ; i < n; i++) { if (isPrime(arr.get(i))) { // If the current element is prime, check // the subsequent non-prime positions if ((i + 3 ) >= n) { break ; } int j = 0 ; while (j < np && (i + nonPrimeNumbers.get(j) - 1 ) < n) { // Check if the number in the non-prime // position is not prime if (!isPrime(arr.get( i + nonPrimeNumbers.get(j) - 1 ))) { return false ; } j++; } } } return true ; } // Driver code public static void main(String[] args) { List<Integer> arr = List.of( 5 , 9 , 3 , 7 , 8 , 2 ); int n = arr.size(); // Function call if (check(arr, n)) { System.out.println( "Prime" ); } else { System.out.println( "Non Prime" ); } } } // This code is contributed by Susobhan Akhuli |
Python3
# Python code for the above approach import math def is_prime(n: int ) - > bool : # Check if n = 1 or n = 0 if n < = 1 : return False # Check if n = 2 or n = 3 if n = = 2 or n = = 3 : return True # Check whether n is divisible by 2 or 3 if n % 2 = = 0 or n % 3 = = 0 : return False # Check from 5 to square root of n # Iterate i by (i + 6) for i in range ( 5 , int (math.sqrt(n)) + 1 , 6 ): if n % i = = 0 or n % (i + 2 ) = = 0 : return False return True def check(arr, n): # Store all possible non-prime indxes non_prime_numbers = [] for i in range ( 2 , n + 1 ): if ( not is_prime(i)): non_prime_numbers.append(i) np = len (non_prime_numbers) # Iterate over range n for i in range (n): # Check if prime or not if (is_prime(arr[i])): # If lowest value of non-prime number is # out of the range for current index # then we don't have to calculate # for the remainings if ((i + 3 ) > = n): break j = 0 # Check for prme numbers in non-prime # indexesas per current index i while (j < np and (i + non_prime_numbers[j] - 1 ) < n): if ( not is_prime(arr[i + non_prime_numbers[j] - 1 ])): return False j + = 1 return True # Driver's code if __name__ = = "__main__" : arr = [ 5 , 9 , 3 , 7 , 8 , 2 ] n = len (arr) # Function call if (check(arr, n)): print ( "Prime" ) else : print ( "Non Prime" ) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to check if a number is prime static bool IsPrime( int n) { if (n <= 1) { return false ; } if (n == 2 || n == 3) { return true ; } if (n % 2 == 0 || n % 3 == 0) { return false ; } // Check divisibility by numbers of the form 6k ± 1 for ( int i = 5; i <= Math.Sqrt(n); i += 6) { if (n % i == 0 || n % (i + 2) == 0) { return false ; } } return true ; } // Function to check if the given array satisfies the // conditions static bool Check(List< int > arr, int n) { List< int > non_prime_numbers = new List< int >(); // Find all non-prime numbers in the range [2, n] for ( int i = 2; i <= n; i++) { if (!IsPrime(i)) { non_prime_numbers.Add(i); } } int np = non_prime_numbers.Count; // Iterate over the array elements for ( int i = 0; i < n; i++) { if (IsPrime(arr[i])) { // If the current element is prime, check // the subsequent non-prime positions if ((i + 3) >= n) { break ; } int j = 0; while (j < np && (i + non_prime_numbers[j] - 1) < n) { // Check if the number in the non-prime // position is not prime if (!IsPrime( arr[i + non_prime_numbers[j] - 1])) { return false ; } j++; } } } return true ; } static void Main( string [] args) { List< int > arr = new List< int >{ 5, 9, 3, 7, 8, 2 }; int n = arr.Count; // Function call if (Check(arr, n)) { Console.WriteLine( "Prime" ); } else { Console.WriteLine( "Non Prime" ); } } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript code for the above approach // Function to check if a number is prime function isPrime(n) { if (n <= 1) { return false ; } if (n === 2 || n === 3) { return true ; } if (n % 2 === 0 || n % 3 === 0) { return false ; } // Check divisibility by numbers of the form 6k ± 1 for (let i = 5; i <= Math.sqrt(n); i += 6) { if (n % i === 0 || n % (i + 2) === 0) { return false ; } } return true ; } // Function to check if the given array satisfies the conditions function check(arr, n) { const nonPrimeNumbers = []; // Find all non-prime numbers in the range [2, n] for (let i = 2; i <= n; i++) { if (!isPrime(i)) { nonPrimeNumbers.push(i); } } const np = nonPrimeNumbers.length; // Iterate over the array elements for (let i = 0; i < n; i++) { if (isPrime(arr[i])) { // If the current element is prime, check the subsequent non-prime positions if (i + 3 >= n) { break ; } let j = 0; while (j < np && i + nonPrimeNumbers[j] - 1 < n) { // Check if the number in the non-prime position is not prime if (!isPrime(arr[i + nonPrimeNumbers[j] - 1])) { return false ; } j++; } } } return true ; } // Driver code const arr = [5, 9, 3, 7, 8, 2]; const n = arr.length; // Function call if (check(arr, n)) { console.log( "Prime" ); } else { console.log( "Non Prime" ); } // This code is contributed by Susobhan Akhuli |
Prime
Time Complexity: O(N*sqrt(N)), where N is the size of the array.
Auxiliary Space: O(N), to store non-prime indexes
Contact Us