Maximum Length of Sequence of Sums of prime factors generated by the given operations | 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
let spf = Array . from ( { length : 100005 } , ( _ , i ) => 0 ) ; let prime = Array . from ( { length : 100005 } , ( _ , i ) => 0 ) ; let dp = Array . from ( { length : 100005 } , ( _ , i ) => 0 ) ; function sieve ( ) { prime [ 0 ] = prime [ 1 ] = false ; for ( let i = 2 ; i < 100005 ; i ++ ) prime [ i ] = true ; for ( let i = 2 ; i * i < 100005 ; i ++ ) { if ( prime [ i ] ) { for ( let j = i * i ; j < 100005 ; j += i ) { prime [ j ] = false ; } } } } function smallestPrimeFactors ( ) { for ( let i = 0 ; i < 100005 ; i ++ ) spf [ i ] = - 1 ; for ( let i = 2 ; i * i < 100005 ; i ++ ) { for ( let j = i ; j < 100005 ; j += i ) { if ( spf [ j ] == - 1 ) { spf [ j ] = i ; } } } } function sumOfPrimeFactors ( n ) { let ans = 0 ; while ( n > 1 ) { ans += spf [ n ] ; n /= spf [ n ] ; } return ans ; } function findLength ( n ) { if ( prime [ n ] ) { return 1 ; } if ( dp [ n ] != 0 ) { return dp [ n ] ; } let sum = sumOfPrimeFactors ( n ) ; return dp [ n ] = 1 + findLength ( sum ) ; } function maxLength ( n , m ) { sieve ( ) ; smallestPrimeFactors ( ) ; let ans = Number . MIN_VALUE ; for ( let i = n ; i <= m ; i ++ ) { if ( i == 4 ) { continue ; } ans = Math . max ( ans , findLength ( i ) ) ; } return ans ; } let n = 2 , m = 14 ; document . write ( maxLength ( n , m ) ) ;