pta 7-153 连续因子

直接暴力枚举

这个题目有个很坑的点就是答案一定是从所有因子相乘 可以得到n的因子中去取，我刚开始以为只要是因子就可以了，一直wa第二个点。比如说540，答案应该是3* 4* 5 而不是2* 3* 4* 5* 6
3* 4* 5可以从540 = 3* 4 * 5* 9得到

另外这题说明了数据范围是小于231次方的，根本不会爆int。

AC代码

#include<bits/stdc++.h>
using namespace std;
bool isprime(int x)
{
    for (int i = 2; i <= (int)sqrt(x); i++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    int n;
    cin >> n;
    if (isprime(n)) // 质数就是他本身，优化操作
    {
        cout << "1\n" << n;
        return 0;
    }
    int ans = 0, res = 0, flag = 0;
    // 这里可能会有萌新疑惑为什么取根号就行了
    // 求因子的话，如果一个数是完全平方数，它最大的因子除了本身就是根号
    // 如果不是完全平方数的话，比根号大的因子一定对应一个比根号小的因子
    // 换言之，比根号大的因子的情况已经被比根号小的因子的情况全覆盖了
    for (int i = 2; i <= (int)sqrt(n); i++)
    {
        if (n % i == 0)
        {
            int j = i,temp=n;
            res = 0;
            while (temp % j == 0)
            {
                temp /= j;
                res++;
                j++;  
            }
            if (ans < res) ans = res, flag = i; // flag标记答案
        }
    }
    cout << ans << "\n";
    for (int i = 0; i < ans; i++)
    {
        cout << flag + i;
        if (i < ans - 1) cout << "*";
    }
    return 0;
}