本文概述
- C ++
- Java
- Python3
- C#
对于[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简单的方法：解决问题的最简单方法是在范围内进行迭代[N, M], 对于每个整数, 求出其主要因子并将其求和, 并对获得的总和重复此操作递归地直到获得一个本身就是质数的和。
输出：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
高效方法：可以使用以下方法优化上述方法动态编程。请按照以下步骤解决问题：
- 使用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 SinghPython3
# 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 ] * 100005dp = [ 0 ] * 100005# Function to compute all primes
# using Sieve of Eratosthenes
def sieve():for i in range ( 2 , 100005 ):
prime[i] = Truei = 2
while i * i <
100005 :
if (prime[i]):
for j in range (i * i, 100005 , i):
prime[j] = Falsei + = 1# Function for finding smallest
# prime factors for every integer
def smallestPrimeFactors():for i in range ( 10005 ):
spf[i] = - 1i = 2
while i * i <
100005 :
for j in range (i, 100005 , i):
if (spf[j] = = - 1 ):
spf[j] = ii + = 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 SinghC#
//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)
推荐阅读
- ADP印度面试经验|S1（针对会员技术人员）
- 计算可能的长度为N的二进制字符串，而没有P个连续的0和Q个连续的1
- Salesforce面试经验|校园内
- 查找未排序数组中缺失的最小正数|S1
- Lex程序可计算行，空格和制表符的数量
- Win7可以不激活吗？Win7不激活会怎样样？
- spoon.sys损坏后，win7开机无法进入系统的处理办法
- win7系统关闭“交互式服务检测”提示窗口的办法
- win7定时开机的设置步骤