孙悟空的金箍棒顽皮的孙悟空又大闹天宫了

孙悟空的金箍棒
描述

顽皮的悟空又在大闹天宫了，太上老君觉得悟空太闹腾了，于是让你去收掉悟空的作案工具金箍棒，太上老君给了你一个法宝，可以收掉悟空的金箍棒，但是有个限制，只能放下长度为质数时的金箍棒，例如长度时8，就放不下，但是将他缩短为2就可以放下，但是金箍棒不是你的法宝，你不能随意的变化，需要符合规则（即长度为l，x为l的因子，那么你可以变为l/x的长度，你可以做出任意次这样的操作，知道l为质数）。

例如：l=12，选择12的因子2，此时l=6，再选择6的因子2，此时结果为3，为质数。但是很明显，这个方案不一定是最优的。

day08-02.zip

输入
第一个一个整数T(0<T<1e5)，表示数据组数

其后T行，每行一个整数l,表示金箍棒的长度(l<=1e6)

输出
T行，每行一个整数，表示最少的操作次数

输入样例 1

2
4
3
输出样例 1

1
0

#include <iostream>
#include <cmath>
using namespace std; 
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int minCalc(int l) {
    if (isPrime(l)) {
        return 0;
    }
    for (int i = 2; i <= sqrt(l); i++) {
        if (l % i == 0) {
            return 1 + minCalc(l / i);
        }
    }
    return -1;
}

int main() {
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int l;
        cin >> l;
        int min = minCalc(l);
        cout << min << endl;
    }

    return 0;
}

【以下回答由 GPT 生成】

解题思路：将金箍棒的长度l不断缩短为l/x，直到l为质数为止。由于题目中l的范围为1e6，所以可以使用筛选法来找到所有的质数，然后从l的约数中找到最小的质数。

具体步骤如下：

1. 构建一个辅助数组isPrime，长度为1e6+1，用来标记是否为质数。初始化isPrime的值为true。
2. 使用筛选法，将isPrime数组中的质数的倍数标记为false。首先将isPrime[0]和isPrime[1]置为false，因为0和1不是质数。
3. 从2开始遍历isPrime数组，如果isPrime[i]为true，说明i是质数，那么将isPrime数组中i的倍数的元素都标记为false。
4. 接下来遍历输入的每个长度l，如果l为质数，则操作次数为0。否则，从2开始遍历l的约数，找到最小的质数x，将l缩短为l/x。操作次数加1，继续循环直到l为质数为止。返回操作次数。

Python代码如下：

# 筛选法找到1e6以内的所有质数
def sieve_of_eratosthenes(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = isPrime[1] = False
    p = 2
    while p * p <= n:
        if isPrime[p]:
            for i in range(p * p, n + 1, p):
                isPrime[i] = False
        p += 1
    return isPrime

# 计算最少操作次数
def min_operations(length):
    if isPrime[length]:  # 如果长度本身就是质数，则不需要操作
        return 0
    for i in range(2, length + 1):
        if length % i == 0 and isPrime[i]:  # 找到最小的质数x，将长度缩短为length/x
            return 1 + min_operations(length // i)

# 主函数
if __name__ == "__main__":
    T = int(input())
    isPrime = sieve_of_eratosthenes(10**6)
    for _ in range(T):
        length = int(input())
        print(min_operations(length))

复杂度分析：

筛选法的时间复杂度为O(nloglogn)，计算最少操作次数的时间复杂度为O(sqrt(l))，所以总的时间复杂度为O(T * sqrt(l))。空间复杂度为O(n)。其中T为数据组数，l为金箍棒的长度。

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7650525