Longest sub-array of Prime Numbers using Segmented Sieve
Given an array arr[] of N integers, the task is to find the longest subarray where all numbers in that subarray are prime.
Examples:
Input: arr[] = {3, 5, 2, 66, 7, 11, 8}
Output: 3
Explanation:
Maximum contiguous prime number sequence is {2, 3, 5}Input: arr[] = {1, 2, 11, 32, 8, 9}
Output: 2
Explanation:
Maximum contiguous prime number sequence is {2, 11}
Approach:
For elements of the array in order of 106, we have discussed an approach in this article.
For elements of the array in order of 109, the idea is to use Segmented Sieve to find the Prime Numbers to value upto 109.
Steps:
- Find the Prime Numbers between the range of minimum element and maximum element of the array using the approach discussed in this article.
- After calculating the Prime Numbers between the range. The longest subarray with Prime Numbers can be calculated using Kadane’s Algorithm. Following are the steps:
- Traverse the given array arr[] 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 update max_so_far to current_max.
- If any element is non-prime element, then reset current_max to 0.
Below is the implementation of the above approach:
C++
// C++ program to find longest subarray // of prime numbers #include <bits/stdc++.h> using namespace std; // To store the prime numbers unordered_set< int > allPrimes; // Function that find prime numbers // till limit void simpleSieve( int limit, vector< int >& prime) { bool mark[limit + 1]; memset (mark, false , sizeof (mark)); // Find primes using // Sieve of Eratosthenes for ( int i = 2; i <= limit; ++i) { if (mark[i] == false ) { prime.push_back(i); for ( int j = i; j <= limit; j += i) { mark[j] = true ; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve void primesInRange( int low, int high) { // Find the limit int limit = floor ( sqrt (high)) + 1; // To store the prime numbers vector< int > prime; // Compute all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] int n = high - low + 1; // Declaring boolean for the // range [low, high] bool mark[n + 1]; // Initialise bool[] to false memset (mark, false , sizeof (mark)); // Traverse the prime numbers till // limit for ( int i = 0; i < prime.size(); i++) { int loLim = floor (low / prime[i]); loLim *= prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += prime[i]; } if (loLim == prime[i]) { loLim += prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for ( int j = loLim; j <= high; j += prime[i]) mark[j - low] = true ; } // Element which are not marked in // range are Prime for ( int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.insert(i); } } } // Function that finds longest subarray // of prime numbers int maxPrimeSubarray( int arr[], int n) { int current_max = 0; int max_so_far = 0; for ( int i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.count(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver Code int main() { int arr[] = { 1, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = sizeof (arr) / sizeof (arr[0]); // Find minimum and maximum element int max_el = *max_element(arr, arr + n); int min_el = *min_element(arr, arr + n); // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call cout << maxPrimeSubarray(arr, n); return 0; } |
Java
// Java program to find longest subarray // of prime numbers import java.util.*; import java.lang.*; import java.io.*; class GFG{ // To store the prime numbers static Set<Integer> allPrimes = new HashSet<>(); // Function that find prime numbers // till limit static void simpleSieve( int limit, ArrayList<Integer> prime) { boolean []mark = new boolean [limit + 1 ]; // Find primes using // Sieve of Eratosthenes for ( int i = 2 ; i <= limit; ++i) { if (mark[i] == false ) { prime.add(i); for ( int j = i; j <= limit; j += i) { mark[j] = true ; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve static void primesInRange( int low, int high) { // Find the limit int limit = ( int )Math.floor(Math.sqrt(high)) + 1 ; // To store the prime numbers ArrayList<Integer> prime = new ArrayList<>(); // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] int n = high - low + 1 ; // Declaring boolean for the // range [low, high] boolean []mark = new boolean [n + 1 ]; // Traverse the prime numbers till // limit for ( int i = 0 ; i < prime.size(); i++) { int loLim = ( int )Math.floor(( double )low / ( int )prime.get(i)); loLim *= ( int )prime.get(i); // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += ( int )prime.get(i); } if (loLim == ( int )prime.get(i)) { loLim += ( int )prime.get(i); } // Mark the multiples of prime[i] // in [low, high] as true for ( int j = loLim; j <= high; j += ( int )prime.get(i)) mark[j - low] = true ; } // Element which are not marked in // range are Prime for ( int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.add(i); } } } // Function that finds longest subarray // of prime numbers static int maxPrimeSubarray( int []arr, int n) { int current_max = 0 ; int max_so_far = 0 ; for ( int i = 0 ; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.contains(arr[i])) current_max = 0 ; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code public static void main(String[] args) { int []arr = { 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 }; int n = arr.length; // Find minimum and maximum element int max_el = Integer.MIN_VALUE; int min_el = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call System.out.print(maxPrimeSubarray(arr, n)); } } // This code is contributed by offbeat |
Python3
# Python3 program to find longest subarray # of prime numbers import math # To store the prime numbers allPrimes = set () # Function that find prime numbers # till limit def simpleSieve(limit, prime): mark = [ False ] * (limit + 1 ) # Find primes using # Sieve of Eratosthenes for i in range ( 2 , limit + 1 ): if mark[i] = = False : prime.append(i) for j in range (i, limit + 1 , i): mark[j] = True # Function that finds all prime # numbers in given range using # Segmented Sieve def primesInRange(low, high): # Find the limit limit = math.floor(math.sqrt(high)) + 1 # To store the prime numbers prime = [] # Compute all primes less than # or equals to sqrt(high) # using Simple Sieve simpleSieve(limit, prime) # Count the elements in the # range [low, high] n = high - low + 1 # Declaring and initializing boolean # for the range[low,high] to False mark = [ False ] * (n + 1 ) # Traverse the prime numbers till # limit for i in range ( len (prime)): loLim = low / / prime[i] loLim * = prime[i] # Find the minimum number in # [low..high] that is a # multiple of prime[i] if loLim < low: loLim + = prime[i] if loLim = = prime[i]: loLim + = prime[i] # Mark the multiples of prime[i] # in [low, high] as true for j in range (loLim, high + 1 , prime[i]): mark[j - low] = True # Element which are not marked in # range are Prime for i in range (low, high + 1 ): if not mark[i - low]: allPrimes.add(i) # Function that finds longest subarray # of prime numbers def maxPrimeSubarray(arr, n): current_max = 0 max_so_far = 0 for i in range (n): # If element is Non-prime then # updated current_max to 0 if arr[i] not in allPrimes: current_max = 0 # If element is prime, then # update current_max and # max_so_far else : current_max + = 1 max_so_far = max (current_max, max_so_far) # Return the count of longest # subarray return max_so_far # Driver Code arr = [ 1 , 2 , 4 , 3 , 29 , 11 , 7 , 8 , 9 ] n = len (arr) # Find minimum and maximum element max_el = max (arr) min_el = min (arr) # Find prime in the range # [min_el, max_el] primesInRange(min_el, max_el) # Function call print (maxPrimeSubarray(arr, n)) # This code is contributed by Shivam Singh |
C#
// C# program to find longest subarray // of prime numbers using System; using System.Collections; using System.Collections.Generic; class GFG{ // To store the prime numbers static HashSet< int > allPrimes = new HashSet< int >(); // Function that find prime numbers // till limit static void simpleSieve( int limit, ref ArrayList prime) { bool []mark = new bool [limit + 1]; Array.Fill(mark, false ); // Find primes using // Sieve of Eratosthenes for ( int i = 2; i <= limit; ++i) { if (mark[i] == false ) { prime.Add(i); for ( int j = i; j <= limit; j += i) { mark[j] = true ; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve static void primesInRange( int low, int high) { // Find the limit int limit = ( int )Math.Floor(Math.Sqrt(high)) + 1; // To store the prime numbers ArrayList prime = new ArrayList(); // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, ref prime); // Count the elements in the // range [low, high] int n = high - low + 1; // Declaring boolean for the // range [low, high] bool []mark = new bool [n + 1]; // Initialise bool[] to false Array.Fill(mark, false ); // Traverse the prime numbers till // limit for ( int i = 0; i < prime.Count; i++) { int loLim = ( int )Math.Floor(( double )low / ( int )prime[i]); loLim *= ( int )prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += ( int )prime[i]; } if (loLim == ( int )prime[i]) { loLim += ( int )prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for ( int j = loLim; j <= high; j += ( int )prime[i]) mark[j - low] = true ; } // Element which are not marked in // range are Prime for ( int i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.Add(i); } } } // Function that finds longest subarray // of prime numbers static int maxPrimeSubarray( int []arr, int n) { int current_max = 0; int max_so_far = 0; for ( int i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.Contains(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.Max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code public static void Main( string [] args) { int []arr = { 1, 2, 4, 3, 29, 11, 7, 8, 9 }; int n = arr.Length; // Find minimum and maximum element int max_el = Int32.MinValue; int min_el = Int32.MaxValue; for ( int i = 0; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call Console.Write(maxPrimeSubarray(arr, n)); } } // This code is contributed by rutvik_56 |
Javascript
<script> // Javascript program to find longest subarray // of prime numbers // To store the prime numbers let allPrimes = new Set(); // Function that find prime numbers // till limit function simpleSieve(limit, prime) { let mark = Array.from({length: limit + 1}, (_, i) => 0); // Find primes using // Sieve of Eratosthenes for (let i = 2; i <= limit; ++i) { if (mark[i] == false ) { prime.push(i); for (let j = i; j <= limit; j += i) { mark[j] = true ; } } } } // Function that finds all prime // numbers in given range using // Segmented Sieve function primesInRange(low, high) { // Find the limit let limit = Math.floor(Math.sqrt(high)) + 1; // To store the prime numbers let prime = []; // Comput all primes less than // or equals to sqrt(high) // using Simple Sieve simpleSieve(limit, prime); // Count the elements in the // range [low, high] let n = high - low + 1; // Declaring boolean for the // range [low, high] let mark = Array.from({length: n + 1}, (_, i) => 0); // Traverse the prime numbers till // limit for (let i = 0; i < prime.length; i++) { let loLim = Math.floor(low / prime[i]); loLim *= prime[i]; // Find the minimum number in // [low..high] that is a // multiple of prime[i] if (loLim < low) { loLim += prime[i]; } if (loLim == prime[i]) { loLim += prime[i]; } // Mark the multiples of prime[i] // in [low, high] as true for (let j = loLim; j <= high; j += prime[i]) mark[j - low] = true ; } // Element which are not marked in // range are Prime for (let i = low; i <= high; i++) { if (!mark[i - low]) { allPrimes.add(i); } } } // Function that finds longest subarray // of prime numbers function maxPrimeSubarray(arr, n) { let current_max = 0; let max_so_far = 0; for (let i = 0; i < n; i++) { // If element is Non-prime then // updated current_max to 0 if (!allPrimes.has(arr[i])) current_max = 0; // If element is prime, then // update current_max and // max_so_far else { current_max++; max_so_far = Math.max(current_max, max_so_far); } } // Return the count of longest // subarray return max_so_far; } // Driver code let arr = [ 1, 2, 4, 3, 29, 11, 7, 8, 9 ]; let n = arr.length; // Find minimum and maximum element let max_el = Number.MIN_VALUE; let min_el = Number.MAX_VALUE; for (let i = 0; i < n; i++) { if (arr[i] < min_el) { min_el = arr[i]; } if (arr[i] > max_el) { max_el = arr[i]; } } // Find prime in the range // [min_el, max_el] primesInRange(min_el, max_el); // Function call document.write(maxPrimeSubarray(arr, n)); </script> |
4
Time Complexity: O(N), where N is the length of the array.
Auxiliary Space: O(N), where N is the length of the array.
Contact Us