Given an array arr[] of length N, the task is to find the number of subarrays that consists of prime numbers in ascending order.
Examples:
Input: arr[] = [8, 5, 6, 3, 7]
Output: 4
Explanation: All possible subarrays whose elements are prime and also in ascending order are {5}, {3}, {7} and {3, 7}.Input: arr[] = [4, 8, 2, 7, 11, 6]
Output: 6
Explanation: All possible subarrays whose elements are prime and also in ascending order are {2}, {7}, {11}, {2, 7}, {7, 11} and {2, 7, 11}.
Approach: This can be solved with the following idea:
Using a sliding window approach, total number of prime subarrays can be counted.
Below are the steps involved in the implementation of the code:
- Initialize ans to 0.
- Iterate over the array, and for each element and do the following:
- If the element is not a prime number, continue iterating.
- If the element is a prime number, Initialize count to 0, and last_prime to the value of that element.
- While the next element is a prime number and greater than or equal to the value of last_prime, increment count and moves to the next element.
- Once the loop is done, add (count * (count + 1)) / 2 with ans as this is equivalent to adding the number of subarrays that can be formed with count consecutive elements.
- Finally, return the ans.
Below is the implementation of the above approach:
C++
// CPP program of the above approach#include <cmath>#include <iostream>using namespace std;// Function to check if n is prime or notbool 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; for (int i = 5; i <= sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true;}// Function to count subarrays with// ascending primeslong long int ordered_prime_subarrays(int Arr[], int N){ long long int ans = 0; for (int i = 0; i < N; i++) { if (is_prime(Arr[i])) { int count = 0; int last_prime = Arr[i]; while (i < N && is_prime(Arr[i]) && Arr[i] >= last_prime) { count++; i++; } ans += (count * (count + 1)) / 2; } } return ans;}// Driver codeint main(){ int Arr[] = { 8, 5, 6, 3, 7 }; int N = sizeof(Arr) / sizeof(Arr[0]); // Function call cout << ordered_prime_subarrays(Arr, N) << endl; return 0;} |
Java
// JAVA proagram to find number of prime sorted subarraysimport java.lang.Math;public class GFG { // Function to check if n is prime or not public 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; for (int i = 5; i <= Math.sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to count subarrays with ascending primes public static long orderedPrimeSubarrays(int[] Arr, int N) { long ans = 0; for (int i = 0; i < N; i++) { if (isPrime(Arr[i])) { int count = 0; int lastPrime = Arr[i]; while (i < N && isPrime(Arr[i]) && Arr[i] >= lastPrime) { count++; i++; } ans += (count * (count + 1)) / 2; } } return ans; } // Driver code public static void main(String[] args) { int[] Arr = { 8, 5, 6, 3, 7 }; int N = Arr.length; // Function call System.out.println(orderedPrimeSubarrays(Arr, N)); }}// This code is contributed by shivamgupta0987654321 |
Python3
import math# Function to check if n is prime or notdef is_prime(n): if n <= 1: return False if n == 2 or n == 3: return True if n % 2 == 0 or n % 3 == 0: return False for i in range(5, int(math.sqrt(n)) + 1, 6): if n % i == 0 or n % (i + 2) == 0: return False return True# Function to count subarrays with ascending primesdef ordered_prime_subarrays(arr): ans = 0 n = len(arr) i = 0 while i < n: if is_prime(arr[i]): count = 0 last_prime = arr[i] while i < n and is_prime(arr[i]) and arr[i] >= last_prime: count += 1 i += 1 ans += (count * (count + 1)) // 2 else: i += 1 return ans# Driver codeif __name__ == "__main__": arr = [8, 5, 6, 3, 7] # Function call print(ordered_prime_subarrays(arr))# This code is contributed by shivamgupta310570 |
C#
// C# program of the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check if n is prime or not 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; for (int i = 5; i <= Math.Sqrt(n); i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to count subarrays with // ascending primes static long OrderedPrimeSubarrays(int[] arr, int n) { long ans = 0; for (int i = 0; i < n; i++) { if (IsPrime(arr[i])) { int count = 0; int lastPrime = arr[i]; while (i < n && IsPrime(arr[i]) && arr[i] >= lastPrime) { count++; i++; } ans += (count * (count + 1)) / 2; } } return ans; } // Driver code static void Main(string[] args) { int[] arr = { 8, 5, 6, 3, 7 }; int n = arr.Length; // Function call Console.WriteLine(OrderedPrimeSubarrays(arr, n)); }}// This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript program of the above approach// Function to check if n is prime or notfunction is_prime(n) { if (n <= 1) return false; if (n === 2 || n === 3) return true; if (n % 2 === 0 || n % 3 === 0) return false; for (let i = 5; i <= Math.sqrt(n); i = i + 6) { if (n % i === 0 || n % (i + 2) === 0) return false; } return true;}// Function to count subarrays with ascending primesfunction ordered_prime_subarrays(Arr, N) { let ans = 0; for (let i = 0; i < N; i++) { if (is_prime(Arr[i])) { let count = 0; let last_prime = Arr[i]; while (i < N && is_prime(Arr[i]) && Arr[i] >= last_prime) { count++; i++; } ans += (count * (count + 1)) / 2; } } return ans;}// Driver codelet Arr = [8, 5, 6, 3, 7];let N = Arr.length;// Function callconsole.log(ordered_prime_subarrays(Arr, N));// This code is contributed by Susobhan Akhuli |
Output
4
Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(1)
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!
