c++ - 前20个自然数的LCM

Question

我有一些代码可以计算出前 20 个自然数的最小公倍数。

在这里。

const bool IsPrime(const unsigned long long number) {
    cout<<"checking if "<<number<<" is prime.\n";
    //If a number cannot be divided by any number up to 
    //half of it, then that number is prime.
    for (unsigned long long i = 2; i<=number/2; ++i) {
        if (number%i==0) {
            cout<<number<<" is not prime.\n";
            return false;
        }
    }
    //the number seems to be prime.
    cout<<number<<" is PRIME.\n";
    return true;
}

vector<int> PrimeFactorize(int number) {
    cout<<"Prime factorizing "<<number<<"\n";
    vector<int> prime_factors;
    for (int num = 2; !IsPrime(number); ++num) {
        if (number%num==0&&IsPrime(num)) {
            cout<<number<<" is divisible by "<<num<<" and "<<num<<" is PRIME.\n";
            number /= num;
            prime_factors.push_back(num);
            num = 1;
        }
    }
    prime_factors.push_back(number);
    return prime_factors;
 }

void Problem5( ) {
    vector<int> prime_factors[19];
    int max_prime_powers[19] = {0};
    //prime factorize all the numbers.
    for (int i = 2; i<=20; ++i) {
        prime_factors[i-2] = PrimeFactorize(i);
        int temp_max_powers[19] = {0};

    for (auto& prime_factor:prime_factors[i-2]) {
        ++temp_max_powers[prime_factor];
    }

    //compare powers obtained and update the
    //max_prime_factors
    for (int u = 0; u<19; ++u) {
        if (max_prime_powers[u]<temp_max_powers[u]) {
            max_prime_powers[u] = temp_max_powers[u];
        }
    }
}

//now multiply all the things together to get the lcm.
int LCM=1;
for (int y = 2; y<19; ++y) {
    LCM *= (y^(max_prime_powers[y]));
}

cout<<"\n\n\n the answer is "<<LCM<<"\n";

}

我试着单步执行它，它做了它应该做的事情，直到我到达最后一个循环，在这个循环中我将所有素数与幂相乘以获得 lcm。计算没有按预期工作。即使代码显示正确的东西，它也会错误地进行计算。

函数返回后，出现运行时错误

Run-Time Check Failure #2 - Stack around the variable 'temp_max_powers' was corrupted.

怎么了？ temp_max_powers 如何破坏堆栈？

我正在使用 visual studio professional 13。这是编译器错误吗？

更新 根据评论，我更正了那里的代码而不是

LCM *= (y^(max_prime_powers[y]));

我现在有

LCM *= _Pow_int(y,(max_prime_powers[y]));

这没有给我正确的答案，错误仍然弹出。

Answer 1

问题一

LCM *= (y^(max_prime_powers[y]));

a^b在 C++/

中不用于 a^b

问题2

为 20 个数字的 LCM 选择 int 可能不是一个好的选择，因为它可能会溢出。

问题3

for (auto& prime_factor:prime_factors[i-2]) {
    ++temp_max_powers[prime_factor];
}

在这里你应该通过打印 prime_factor 的值来调试, 它可能 19或更多导致 UB。 (例如堆栈损坏)

而不是 int temp_max_powers[19] , 你应该使用 std::map<int, int> temp_max_powers

计算LCM的更好算法
如果您能确保在乘法过程中没有整数溢出，您可以使用以下观察结果来计算 LCM。

1. LCM(a, b) = a * b / GCD(a, b)//您可以使用 euclidean method 快速计算 GCD
2. LCM(a1, a2, a3, ... an) = LCM(a1, LCM(a2, a3, ... an))