Maximum no. of contiguous Prime Numbers in an array

0 0 8 minutes read

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

Output

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>

Output

Time Complexity: O(N)

Space Complexity: O(N)

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 zambiatek!