smallest-value-after-replacing-with-sum-of-prime-factors

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer <code>n</code>.

Continuously replace <code>n</code> with the sum of its prime factors.

<ul>
	<li>Note that if a prime factor divides <code>n</code> multiple times, it should be included in the sum as many times as it divides <code>n</code>.</li>
</ul>

Return the smallest value <code>n</code> will take on.

&nbsp;
Example 1:

<pre>
Input: n = 15
Output: 5
Explanation: Initially, n = 15.
15 = 3 * 5, so replace n with 3 + 5 = 8.
8 = 2 * 2 * 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 * 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.
</pre>

Example 2:

<pre>
Input: n = 3
Output: 3
Explanation: Initially, n = 3.
3 is the smallest value n will take on.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 105</code></li>
</ul>

smallestValue

Smallest Value After Replacing With Sum of Prime Factors

Happy Number

happy-number

快乐数

2 Keys Keyboard

2-keys-keyboard

两个键的键盘

Count Ways to Make Array With Product

count-ways-to-make-array-with-product

生成乘积数组的方案数

Distinct Prime Factors of Product of Array

distinct-prime-factors-of-product-of-array

数组乘积中的不同质因数数目

Minimum Division Operations to Make Array Non Decreasing

minimum-division-operations-to-make-array-non-decreasing

使数组非递减的最少除法操作次数

Math

Number Theory

Simulation

给你一个正整数 <code>n</code> 。

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

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

返回 <code>n</code> 可以取到的最小值。

&nbsp;

示例 1：

<pre>输入：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 可以取到的最小值。
</pre>

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= n &lt;= 105</code></li>
</ul>