text: Length of longest subsequence having sum of digits of each element as a Composite Number | C ++ implementation of the above approach ; Function to generate prime numbers using Sieve of Eratosthenes ; Set 0 and 1 as non - prime ; If p is a prime ; Set all multiples of p as non - prime ; Function to find the digit sum of a given number ; Stores the sum of digits ; Extract digits and add to the sum ; Return the sum of the digits ; Function to find the longest subsequence with sum of digits of each element equal to a composite number ; Calculate sum of digits of current array element ; If sum of digits equal to 1 ; If sum of digits is a prime ; Driver Code ; Function call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE void SieveOfEratosthenes ( bool prime [ ] , int p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } int digitSum ( int number ) { int sum = 0 ; while ( number > 0 ) { sum += ( number % 10 ) ; number /= 10 ; } return sum ; } void longestCompositeDigitSumSubsequence ( int arr [ ] , int n ) { int count = 0 ; bool prime [ N + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( prime , N ) ; for ( int i = 0 ; i < n ; i ++ ) { int res = digitSum ( arr [ i ] ) ; if ( res == 1 ) { continue ; } if ( ! prime [ res ] ) { count ++ ; } } cout << count << endl ; } int main ( ) { int arr [ ] = { 13 , 55 , 7 , 3 , 5 , 1 , 10 , 21 , 233 , 144 , 89 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; longestCompositeDigitSumSubsequence ( arr , n ) ; return 0 ; }