Maximum no. of contiguous Prime Numbers in an array
Given an array arr[] of N elements. The task is to find the maximum number of the contiguous prime numbers in the given array.
Examples:
Input: arr[] = {3, 5, 2, 66, 7, 11, 8} Output: 3 Maximum contiguous prime number sequence is {2, 3, 5} Input: arr[] = {1, 0, 2, 11, 32, 8, 9} Output: 2 Maximum contiguous prime number sequence is {2, 11}
Brute Force Approach:
The approach is to first find all the prime numbers that are present in the given array. Then, we traverse through the array and for every element, we check if it is prime or not. If it is prime, we keep incrementing the count of prime numbers in the current contiguous sequence. If it is not prime, we check if the count of prime numbers in the current sequence is greater than the maximum count seen so far. If yes, we update the maximum count. Finally, we return the maximum count.
Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to check if a number is prime bool isPrime( int n) { if (n <= 1) { return false ; } for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) { return false ; } } return true ; } // Function to find the maximum contiguous // prime numbers in the array int maxContiguousPrime( int arr[], int n) { int maxCount = 0; // Maximum count of contiguous primes for ( int i = 0; i < n; i++) { int count = 0; // Count of contiguous primes from index i for ( int j = i; j < n; j++) { if (isPrime(arr[j])) { count++; } else { break ; } } maxCount = max(maxCount, count); } return maxCount; } // Driver code int main() { int arr[] = {3, 5, 2, 66, 7, 11, 8}; int n = sizeof (arr) / sizeof (arr[0]); cout << maxContiguousPrime(arr, n) << endl; return 0; } |
Java
import java.util.*; class GFG { // Function to check if a number is prime static boolean isPrime( int n) { if (n <= 1 ) { return false ; } for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return false ; } } return true ; } // Function to find the maximum contiguous // prime numbers in the array static int maxContiguousPrime( int [] arr, int n) { int maxCount = 0 ; // Maximum count of contiguous primes for ( int i = 0 ; i < n; i++) { int count = 0 ; // Count of contiguous primes // from index i for ( int j = i; j < n; j++) { if (isPrime(arr[j])) { count++; } else { break ; } } maxCount = Math.max(maxCount, count); } return maxCount; } // Driver code public static void main(String[] args) { int [] arr = { 3 , 5 , 2 , 66 , 7 , 11 , 8 }; int n = arr.length; System.out.println(maxContiguousPrime(arr, n)); } } // This code is contributed by prasad264 |
Python3
import math # Function to check if a number is prime def isPrime(n): if n < = 1 : return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : return False return True # Function to find the maximum contiguous prime numbers in the array def maxContiguousPrime(arr): n = len (arr) maxCount = 0 # Maximum count of contiguous primes for i in range (n): count = 0 # Count of contiguous primes from index i for j in range (i, n): if isPrime(arr[j]): count + = 1 else : break maxCount = max (maxCount, count) return maxCount # Driver code arr = [ 3 , 5 , 2 , 66 , 7 , 11 , 8 ] print (maxContiguousPrime(arr)) # Output: 3 |
C#
using System; namespace ConsoleApp1 { class Program { // Function to check if a number is prime static bool IsPrime( int n) { if (n <= 1) { return false ; } for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false ; } } return true ; } // Function to find the maximum contiguous // prime numbers in the array static int MaxContiguousPrime( int [] arr, int n) { int maxCount = 0; // Maximum count of contiguous primes for ( int i = 0; i < n; i++) { int count = 0; // Count of contiguous primes // from index i for ( int j = i; j < n; j++) { if (IsPrime(arr[j])) { count++; } else { break ; } } maxCount = Math.Max(maxCount, count); } return maxCount; } // Driver code static void Main( string [] args) { int [] arr = { 3, 5, 2, 66, 7, 11, 8 }; int n = arr.Length; Console.WriteLine(MaxContiguousPrime(arr, n)); Console.ReadLine(); } } } // This code is contributed by sarojmcy2e |
Javascript
// Function to check if a number is prime function isPrime(n) { if (n <= 1) { return false ; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false ; } } return true ; } // Function to find the maximum contiguous // prime numbers in the array function maxContiguousPrime(arr) { let n = arr.length; let maxCount = 0; // Maximum count of contiguous primes for (let i = 0; i < n; i++) { let count = 0; // Count of contiguous primes from index i for (let j = i; j < n; j++) { if (isPrime(arr[j])) { count++; } else { break ; } } maxCount = Math.max(maxCount, count); } return maxCount; } // Driver code let arr = [3, 5, 2, 66, 7, 11, 8]; console.log(maxContiguousPrime(arr)); // Output: 3 |
3
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Approach:
- Create a sieve to check whether an element is prime or not in O(1).
- Traverse the array with two variables named current_max and max_so_far.
- If a prime number is found then increment current_max and compare it with max_so_far.
- If current_max is greater than max_so_far, then assign max_so_far with current_max
- Every time a non-prime element is found reset current_max to 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; void SieveOfEratosthenes( bool prime[], int p_size) { // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * p; i <= p_size; i += p) prime[i] = false ; } } } // Function that finds // maximum contiguous subarray of prime numbers int maxPrimeSubarray( int arr[], int n) { int max_ele = *max_element(arr, arr+n); bool prime[max_ele + 1]; memset (prime, true , sizeof (prime)); SieveOfEratosthenes(prime, max_ele); int current_max = 0, max_so_far = 0; for ( int i = 0; i < n; i++) { // check if element is non-prime if (prime[arr[i]] == false ) current_max = 0; // If element is prime, then update // current_max and max_so_far accordingly. else { current_max++; max_so_far = max(current_max, max_so_far); } } return max_so_far; } // Driver code int main() { int arr[] = { 1, 0, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = sizeof (arr) / sizeof (arr[0]); cout << maxPrimeSubarray(arr, n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { static void SieveOfEratosthenes( boolean prime[], int p_size) { // false here indicates // that it is not prime prime[ 0 ] = false ; prime[ 1 ] = false ; for ( int p = 2 ; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * p; i <= p_size; i += p) prime[i] = false ; } } } // Function that finds // maximum contiguous subarray of prime numbers static int maxPrimeSubarray( int arr[], int n) { int max_ele = Arrays.stream(arr).max().getAsInt(); boolean prime[] = new boolean [max_ele + 1 ]; Arrays.fill(prime, true ); SieveOfEratosthenes(prime, max_ele); int current_max = 0 , max_so_far = 0 ; for ( int i = 0 ; i < n; i++) { // check if element is non-prime if (prime[arr[i]] == false ) current_max = 0 ; // If element is prime, then update // current_max and max_so_far accordingly. else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } return max_so_far; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 0 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 }; int n = arr.length; System.out.print(maxPrimeSubarray(arr, n)); } } /* This code contributed by PrinciRaj1992 */ |
Python 3
# Python3 implementation of # the approach def SieveOfEratosthenes( prime, p_size): # false here indicates # that it is not prime prime[ 0 ] = False prime[ 1 ] = False for p in range ( 2 ,p_size + 1 ): if (p * p>p_size): break # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p, # set them to non-prime i = p * p while (i< = p_size): prime[i] = False i = i + p # Function that finds # maximum contiguous subarray of prime numbers def maxPrimeSubarray( arr, n): max_ele = max (arr) prime = [ True ] * (max_ele + 1 ) SieveOfEratosthenes(prime, max_ele) current_max = 0 max_so_far = 0 for i in range (n): # check if element is non-prime if (prime[arr[i]] = = False ): current_max = 0 # If element is prime, then update # current_max and max_so_far accordingly. else : current_max = current_max + 1 max_so_far = max (current_max, max_so_far) return max_so_far # Driver code if __name__ = = '__main__' : arr = [ 1 , 0 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 ] n = len (arr) print (maxPrimeSubarray(arr, n)) # this code is contributed by # ash264 |
C#
// C# implementation of the approach using System; using System.Linq; class GFG { static void SieveOfEratosthenes( bool []prime, int p_size) { // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * p; i <= p_size; i += p) prime[i] = false ; } } } // Function that finds maximum // contiguous subarray of prime numbers static int maxPrimeSubarray( int []arr, int n) { int max_ele = arr.Max(); bool []prime = new bool [max_ele + 1]; for ( int i = 0; i < max_ele + 1; i++) prime[i]= true ; SieveOfEratosthenes(prime, max_ele); int current_max = 0, max_so_far = 0; for ( int i = 0; i < n; i++) { // check if element is non-prime if (prime[arr[i]] == false ) current_max = 0; // If element is prime, then update // current_max and max_so_far accordingly. else { current_max++; max_so_far = Math.Max(current_max, max_so_far); } } return max_so_far; } // Driver code public static void Main(String[] args) { int []arr = { 1, 0, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = arr.Length; Console.Write(maxPrimeSubarray(arr, n)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach function SieveOfEratosthenes(prime, p_size) { // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for ( var p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( var i = p * p; i <= p_size; i += p) prime[i] = false ; } } } // Function that finds // maximum contiguous subarray of prime numbers function maxPrimeSubarray(arr, n) { var max_ele = arr.reduce((a,b) => Math.max(a,b)); var prime = Array(max_ele+1).fill( true ); SieveOfEratosthenes(prime, max_ele); var current_max = 0, max_so_far = 0; for ( var i = 0; i < n; i++) { // check if element is non-prime if (prime[arr[i]] == false ) current_max = 0; // If element is prime, then update // current_max and max_so_far accordingly. else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } return max_so_far; } // Driver code var arr = [ 1, 0, 2, 4, 3, 29, 11, 7, 8, 9 ]; var n = arr.length; document.write( maxPrimeSubarray(arr, n)); </script> |
4
Time Complexity: O(N)
Space Complexity: O(N)