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

我有一些代码可以让我获得前20个自然数的LCM。

这里是。

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 Professional13。这是编译器错误吗？

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

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

我现在有

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

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

最佳答案

问题1

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

a^b在C ++ /中不用于ab

问题2

为LCM选择20个数字的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。


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

关于c++ - 前20个自然数的LCM，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27813670/