跳到主要内容

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

链接：2507.使用质因数之和替换后可以取到的最小值
难度：Medium
标签：数学、数论、模拟
简介：给你一个正整数 n 。返回 n 可以取到的最小值。

题解 1 - cpp​

  • 编辑时间：2022-12-18
  • 执行用时：4ms
  • 内存消耗：5.9MB
  • 编程语言：cpp
  • 解法介绍：dfs。
class Solution {
public:
    unordered_map<int, int> m;
    int smallestValue(int n) {
        int ans = n;
        if (isPrime(n)) return n;
        if (m.count(n)) return m[n];
        int num = 0;
        for (int i = 2; i <= n; i++) {
            if (n % i != 0) continue;
            while (n % i == 0) n /= i, num += i;
        }
        m[ans] = num;
        return min(ans, smallestValue(num));
    }
    bool isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
};