C++ 代码优化：寻找两个数的最小公倍数和最大公约数

#include #include #include

using namespace std;

const int N = 1000010;

int n; int primes[N], cnt; bool st[N];

int main() { cin >> n;

// 计算质数表
for (int i = 2; i <= n; i ++ )
{
    if (!st[i]) primes[cnt ++ ] = i;
    for (int j = 0; primes[j] <= n / i; j ++ )
    {
        st[primes[j] * i] = true;
        if (i % primes[j] == 0) break;
    }
}

// 优化：从小到大枚举质数 p，然后从 p 的倍数开始标记合数
for (int i = 0; i < cnt; i ++ )
{
    for (int j = primes[i] * 2; j <= n; j += primes[i])
    {
        st[j] = true;
    }
}

int a = 1, b = 1;

// 优化：根据质因子的个数来分类讨论，而不是只根据幂次来判断
for (int i = 0; i < cnt; i ++ )
{
    int p = primes[i];
    int j = 0;
    while (p <= n)
    {
        j ++ ;
        p *= primes[i];
    }
    if (j > 1)
    {
        a *= pow(primes[i], j);
    }
    else if (j == 1)
    {
        if (a * primes[i] < b * (primes[i] - 1))
        {
            a *= primes[i];
        }
        else b *= primes[i] - 1;
    }
}

if (a > b) swap(a, b);
cout << a << ' ' << b << endl;

return 0;

}

// 哪错了内容：代码的主体思路是正确的，但是存在一些小错误：

// 1. 在计算完质数表后，应该从小到大枚举质数 $p$，然后从 $p$ 的倍数开始标记合数，而不是从 $i=2$ 开始依次枚举 $i$，这样可以保证每个合数只会被标记一次。

// 2. 在计算 $a,b$ 的值时，应该在每个质因子的幂次确定后，根据质因子的个数来分类讨论，而不是只根据幂次来判断。当幂次大于 $1$ 时，需要将当前质因子乘上相应的幂次个数；当幂次等于 $1$ 时，需要判断将当前质因子选为 $a$ 还是 $b$ 更优。

// 下面是修改后的代码：