Length of longest subsequence having sum of digits of each element as a Composite Number | Java 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
import java . util . * ; class GFG { static int N = 100005 ; static void SieveOfEratosthenes ( boolean [ ] 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 ; } } } static int digitSum ( int number ) { int sum = 0 ; while ( number > 0 ) { sum += ( number % 10 ) ; number /= 10 ; } return sum ; } static void longestCompositeDigitSumSubsequence ( int [ ] arr , int n ) { int count = 0 ; boolean [ ] prime = new boolean [ N + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) prime [ i ] = true ; SieveOfEratosthenes ( prime , N ) ; for ( int i = 0 ; i < n ; i ++ ) { int res = digitSum ( arr [ i ] ) ; if ( res == 1 ) { continue ; } if ( prime [ res ] == false ) { count ++ ; } } System . out . println ( count ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 13 , 55 , 7 , 3 , 5 , 1 , 10 , 21 , 233 , 144 , 89 } ; int n = arr . length ; longestCompositeDigitSumSubsequence ( arr , n ) ; } }