给定操作生成的质因子求和序列的最大长度

2021年5月1日17:25:34 发表评论 1,154 次浏览

本文概述

给定两个整数N和M，执行如下操作:

对于[N, M]范围内的每个值，计算其质因数的和，然后再计算该和的质因数的和，以此类推。

为每个数组元素生成上述序列并计算序列的长度。

介绍
N = 8
主要因子= {2, 2, 2}。
总和= 2 + 2 + 2 =6。6的素因子= {2, 3}。
Sum = 2 + 3 =5。现在无法进一步减少5。
因此, 序列为{8, 6, 5}。序列的长度是3。

  • 找到产生的这种子序列的最大长度。

例子：

输入：N = 5, M = 10
输出：3
说明：对于N = 5, 序列为{5}, 因此长度为1
对于N = 6, 序列为{6, 5}, 因此长度为2
对于N = 7, 序列是{7}, 所以长度是1
对于N = 8, 序列是{8, 6, 5}, 所以长度是3
对于N = 9, 序列是{9, 6, 5}, 所以长度是3
对于N = 10, 序列是{10, 7}, 所以长度是2
因此, 该范围内序列的最大长度是3。
输入：N = 2, M = 14
输出：4

简单的方法：解决问题的最简单方法是在范围内进行迭代[N, M], 对于每个整数, 求出其主要因子并将其求和, 并对获得的总和重复此操作递归地直到获得一个本身就是质数的和。

高效方法：可以使用以下方法优化上述方法动态编程。请按照以下步骤解决问题：

  • 使用Eratosthenes筛方法。
  • 使用以下公式预先计算每个整数的最小素数以找出素数使用筛子进行素数分解.
  • 现在，对于[N, M]范围内的每个整数，计算素数因子的和，并对得到的和进行递归重复。将序列的长度存储在dp[]数组中，以避免重新计算。如果得到的和是一个素数，存储进一步的计算。
  • 更新获得的最大长度, 并对范围内的每个数字重复上述步骤[N, M], 除4, 这导致无限循环.
  • 打印获得的线长。

下面是上述方法的实现：

C ++

//C++ Program to implement
//the above approach
#include <bits/stdc++.h>
using namespace std;
  
//Smallest prime factor array
int spf[100005];
  
//Stores if a number is prime or not
bool prime[100005];
  
int dp[100005];
  
//Function to compute all primes
//using Sieve of Eratosthenes
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 ;
             }
         }
     }
}
  
//Function for finding smallest
//prime factors for every integer
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;
             }
         }
     }
}
  
//Function to find the sum of
//prime factors of number
int sumOfPrimeFactors( int n)
{
  
     int ans = 0;
     while (n> 1) {
  
         //Add smallest prime
         //factor to the sum
         ans += spf[n];
  
         //Reduce N
         n /= spf[n];
     }
  
     //Return the answer
     return ans;
}
  
//Function to return the length of
//sequence of for the given number
int findLength( int n)
{
  
     //If the number is prime
     if (prime[n]) {
         return 1;
     }
  
     //If a previously computed
     //subproblem occurred
     if (dp[n]) {
         return dp[n];
     }
  
     //Calculate the sum of
     //prime factors
     int sum = sumOfPrimeFactors(n);
  
     return dp[n] = 1 + findLength(sum);
}
  
//Function to return the maximum length
//of sequence for the given range
int maxLength( int n, int m)
{
  
     //Pre-calculate primes
     sieve();
  
     //Precalculate smllest
     //prime factors
     smallestPrimeFactors();
  
     int ans = INT_MIN;
  
     //Iterate over the range
     for ( int i = n; i <= m; i++) {
         if (i == 4) {
             continue ;
         }
  
         //Update maximum length
         ans = max(ans, findLength(i));
     }
  
     return ans;
}
  
//Driver Code
int main()
{
     int n = 2, m = 14;
  
     cout <<maxLength(n, m);
}

Java

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

Python3

# Python3 program to implement
# the above approach
import sys
  
# Smallest prime factor array
spf = [ 0 ] * 100005
  
# Stores if a number is prime or not
prime = [ False ] * 100005
  
dp = [ 0 ] * 100005
  
# Function to compute all primes
# using Sieve of Eratosthenes
def sieve():
  
     for i in range ( 2 , 100005 ):
         prime[i] = True
          
     i = 2
     while i * i <100005 :
         if (prime[i]):
             for j in range (i * i, 100005 , i):
                 prime[j] = False
                  
         i + = 1
  
# Function for finding smallest
# prime factors for every integer
def smallestPrimeFactors():
  
     for i in range ( 10005 ):
         spf[i] = - 1
  
     i = 2
     while i * i <100005 :
         for j in range (i, 100005 , i):
             if (spf[j] = = - 1 ):
                 spf[j] = i
  
         i + = 1
  
# Function to find the sum of
# prime factors of number
def sumOfPrimeFactors(n):
  
     ans = 0
     while (n> 1 ):
  
         # Add smallest prime
         # factor to the sum
         ans + = spf[n]
  
         # Reduce N
         n //= spf[n]
  
     # Return the answer
     return ans
  
# Function to return the length of
# sequence of for the given number
def findLength(n):
  
     # If the number is prime
     if (prime[n]):
         return 1
  
     # If a previously computed
     # subproblem occurred
     if (dp[n]):
         return dp[n]
  
     # Calculate the sum of
     # prime factors
     sum = sumOfPrimeFactors(n)
  
     dp[n] = 1 + findLength( sum )
  
     return dp[n]
  
# Function to return the maximum length
# of sequence for the given range
def maxLength(n, m):
  
     # Pre-calculate primes
     sieve()
  
     # Precalculate smllest
     # prime factors
     smallestPrimeFactors()
  
     ans = - sys.maxsize - 1
  
     # Iterate over the range
     for i in range (n, m + 1 ):
         if (i = = 4 ):
             continue
  
         # Update maximum length
         ans = max (ans, findLength(i))
  
     return ans
  
# Driver Code
n = 2
m = 14
  
# Function call
print (maxLength(n, m))
  
# This code is contributed by Shivam Singh

C#

//C# program to implement
//the above approach
using System;
  
class GFG{
  
//Smallest prime factor array
static int []spf = new int [100005];
  
//Stores if a number is prime or not
static bool []prime = new bool [100005];
  
static int []dp = new int [100005];
  
//Function to compute all primes
//using Sieve of Eratosthenes
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 ;
             }
         }
     }
}
  
//Function for finding smallest
//prime factors for every integer
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;
             }
         }
     }
}
  
//Function to find the sum of
//prime factors of number
static int sumOfPrimeFactors( int n)
{
     int ans = 0;
     while (n> 1)
     {
  
         //Add smallest prime
         //factor to the sum
         ans += spf[n];
  
         //Reduce N
         n /= spf[n];
     }
  
     //Return the answer
     return ans;
}
  
//Function to return the length of
//sequence of for the given number
static int findLength( int n)
{
  
     //If the number is prime
     if (prime[n]) 
     {
         return 1;
     }
  
     //If a previously computed
     //subproblem occurred
     if (dp[n] != 0) 
     {
         return dp[n];
     }
  
     //Calculate the sum of
     //prime factors
     int sum = sumOfPrimeFactors(n);
  
     return dp[n] = 1 + findLength(sum);
}
  
//Function to return the maximum length
//of sequence for the given range
static int maxLength( int n, int m)
{
  
     //Pre-calculate primes
     sieve();
  
     //Precalculate smllest
     //prime factors
     smallestPrimeFactors();
  
     int ans = int .MinValue;
  
     //Iterate over the range
     for ( int i = n; i <= m; i++)
     {
         if (i == 4)
         {
             continue ;
         }
  
         //Update maximum length
         ans = Math.Max(ans, findLength(i));
     }
     return ans;
}
  
//Driver Code
public static void Main(String[] args)
{
     int n = 2, m = 14;
  
     Console.Write(maxLength(n, m));
}
}
  
//This code is contributed by 29AjayKumar

输出如下：

4

时间复杂度：O((NlogN)

辅助空间：O(N)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: