What is the smallest value n will take on?

The smallest value is the prime number that n will eventually reduce to after all prime factorizations are summed.

How do I factorize a number efficiently?

You can use trial division up to sqrt(n) or precompute primes with a sieve for more efficient factorization.

What is the time complexity of this problem?

The time complexity depends on the factorization step, typically O(sqrt(n)) for each iteration. Optimizations can reduce redundant calculations.

How does the iterative process work?

After factorizing n and summing its prime factors, n is replaced with the sum and the process repeats until n stabilizes.

What pattern is this problem related to?

This problem combines number theory with a simulation pattern, specifically focusing on prime factorization and iterative replacement.

#2507

Medium

auto_awesome数学·结合·模拟

LeetCode 题解工作台

使用质因数之和替换后可以取到的最小值

给你一个正整数 n 。请你将 n 的值替换为 n 的质因数之和，重复这一过程。注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。返回 n 可以取到的最小值。示例 1：输入： n = 15 输出： 5 解释：最开始，n = 15 。 15 = 3 * 5…

数学模拟数论

题目描述

给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。

返回 n 可以取到的最小值。

示例 1：

输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。

示例 2：

输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。

提示：

2 <= n <= 10⁵

lightbulb

解题思路

方法一：暴力模拟

根据题意，我们可以得到一个质因数分解的过程，即将一个数不断地分解为质因数，分解不能分解。过程中将每次分解的质因数相加，递归或者迭代地进行即可。

时间复杂度 $O(\sqrt{n})$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def smallestValue(self, n: int) -> int:
        while 1:
            t, s, i = n, 0, 2
            while i <= n // i:
                while n % i == 0:
                    n //= i
                    s += i
                i += 1
            if n > 1:
                s += n
            if s == t:
                return t
            n = s

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands the process of prime factorization and iterative reduction.
question_mark
Candidate shows ability to optimize factorization and apply efficient algorithms.
question_mark
Candidate demonstrates good handling of large input sizes, such as n up to 10^5.

warning

常见陷阱

外企场景

error
Forgetting to handle edge cases where n is already prime.
error
Failing to optimize factorization for large numbers, leading to time complexity issues.
error
Not recognizing that the final result is always a prime number.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement the solution using a sieve of Eratosthenes to precompute primes.
arrow_right_alt
Modify the solution to track the number of iterations required to reach the smallest value.
arrow_right_alt
Add additional constraints where n could be a very large number, requiring more efficient algorithms.

help

常见问题

外企场景

继续练习

#3461 判断操作后字符串中的数字是否相等 I #2513 最小化两个数组中的最大值 #2521 数组乘积中的不同质因数数目