Maximum Length of Sequence of Sums of prime factors generated by the given operations | Python3 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 sys NEW_LINE spf = [ 0 ] * 100005 NEW_LINE prime = [ False ] * 100005 NEW_LINE dp = [ 0 ] * 100005 NEW_LINE def sieve ( ) : NEW_LINE INDENT for i in range ( 2 , 100005 ) : NEW_LINE INDENT prime [ i ] = True NEW_LINE DEDENT i = 2 NEW_LINE while i * i < 100005 : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT for j in range ( i * i , 100005 , i ) : NEW_LINE INDENT prime [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def smallestPrimeFactors ( ) : NEW_LINE INDENT for i in range ( 10005 ) : NEW_LINE INDENT spf [ i ] = - 1 NEW_LINE DEDENT i = 2 NEW_LINE while i * i < 100005 : NEW_LINE INDENT for j in range ( i , 100005 , i ) : NEW_LINE INDENT if ( spf [ j ] == - 1 ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def sumOfPrimeFactors ( n ) : NEW_LINE INDENT ans = 0 NEW_LINE while ( n > 1 ) : NEW_LINE INDENT ans += spf [ n ] NEW_LINE n //= spf [ n ] NEW_LINE DEDENT return ans NEW_LINE DEDENT def findLength ( n ) : NEW_LINE INDENT if ( prime [ n ] ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ n ] ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT sum = sumOfPrimeFactors ( n ) NEW_LINE dp [ n ] = 1 + findLength ( sum ) NEW_LINE return dp [ n ] NEW_LINE DEDENT def maxLength ( n , m ) : NEW_LINE INDENT sieve ( ) NEW_LINE smallestPrimeFactors ( ) NEW_LINE ans = - sys . maxsize - 1 NEW_LINE for i in range ( n , m + 1 ) : NEW_LINE INDENT if ( i == 4 ) : NEW_LINE INDENT continue NEW_LINE DEDENT ans = max ( ans , findLength ( i ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT n = 2 NEW_LINE m = 14 NEW_LINE print ( maxLength ( n , m ) ) NEW_LINE