Maximum Length of Sequence of Sums of prime factors generated by the given operations | Java Program to implement the above approach ; Smallest prime factor array ; Stores if a number is prime or not ; Function to compute all primes using Sieve of Eratosthenes ; Function for finding smallest prime factors for every integer ; Function to find the sum of prime factors of number ; Add smallest prime factor to the sum ; Reduce N ; Return the answer ; Function to return the length of sequence of for the given number ; If the number is prime ; If a previously computed subproblem occurred ; Calculate the sum of prime factors ; Function to return the maximum length of sequence for the given range ; Pre - calculate primes ; Precalculate smallest prime factors ; Iterate over the range ; Update maximum length ; Driver Code
import java . util . * ; class GFG { static int spf [ ] = new int [ 100005 ] ; static boolean prime [ ] = new boolean [ 100005 ] ; static int dp [ ] = new int [ 100005 ] ; static void sieve ( ) { prime [ 0 ] = prime [ 1 ] = false ; for ( int i = 2 ; i < 100005 ; i ++ ) prime [ i ] = true ; for ( int i = 2 ; i * i < 100005 ; i ++ ) { if ( prime [ i ] ) { for ( int j = i * i ; j < 100005 ; j += i ) { prime [ j ] = false ; } } } } static void smallestPrimeFactors ( ) { for ( int i = 0 ; i < 100005 ; i ++ ) spf [ i ] = - 1 ; for ( int i = 2 ; i * i < 100005 ; i ++ ) { for ( int j = i ; j < 100005 ; j += i ) { if ( spf [ j ] == - 1 ) { spf [ j ] = i ; } } } } static int sumOfPrimeFactors ( int n ) { int ans = 0 ; while ( n > 1 ) { ans += spf [ n ] ; n /= spf [ n ] ; } return ans ; } static int findLength ( int n ) { if ( prime [ n ] ) { return 1 ; } if ( dp [ n ] != 0 ) { return dp [ n ] ; } int sum = sumOfPrimeFactors ( n ) ; return dp [ n ] = 1 + findLength ( sum ) ; } static int maxLength ( int n , int m ) { sieve ( ) ; smallestPrimeFactors ( ) ; int ans = Integer . MIN_VALUE ; for ( int i = n ; i <= m ; i ++ ) { if ( i == 4 ) { continue ; } ans = Math . max ( ans , findLength ( i ) ) ; } return ans ; } public static void main ( String [ ] args ) { int n = 2 , m = 14 ; System . out . print ( maxLength ( n , m ) ) ; } }