Subarray of size K with prime sum | C ++ program to implement the above approach ; Generate all prime numbers in the range [ 1 , 1000000 ] ; Set all numbers as prime initially ; Mark 0 and 1 as non - prime ; If current element is prime ; Mark all its multiples as non - prime ; Function to print the subarray whose sum of elements is prime ; Store the current subarray of size K ; Calculate the sum of first K elements ; Check if currSum is prime ; Store the start and last index of subarray of size K ; Iterate over remaining array ; Check if currSum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void sieve ( bool prime [ ] ) { for ( int i = 0 ; i < 1000000 ; i ++ ) { prime [ i ] = true ; } prime [ 0 ] = prime [ 1 ] = false ; for ( int i = 2 ; i * i <= 1000000 ; i ++ ) { if ( prime [ i ] ) { for ( int j = i * i ; j <= 1000000 ; j += i ) { prime [ j ] = false ; } } } } void subPrimeSum ( int N , int K , int arr [ ] , bool prime [ ] ) { int currSum = 0 ; for ( int i = 0 ; i < K ; i ++ ) { currSum += arr [ i ] ; } if ( prime [ currSum ] ) { for ( int i = 0 ; i < K ; i ++ ) { cout << arr [ i ] << " ▁ " ; } return ; } int st = 1 , en = K ; while ( en < N ) { currSum += arr [ en ] - arr [ st - 1 ] ; if ( prime [ currSum ] ) { for ( int i = st ; i <= en ; i ++ ) { cout << arr [ i ] << " ▁ " ; } return ; } en ++ ; st ++ ; } } int main ( ) { int arr [ ] = { 20 , 7 , 5 , 4 , 3 , 11 , 99 , 87 , 23 , 45 } ; int K = 4 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; bool prime [ 1000000 ] ; sieve ( prime ) ; subPrimeSum ( N , K , arr , prime ) ; }