LCM первых 20 натуральных чисел

Question

У меня есть код, который должен получить мне LCM из первых 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 повреждает стек?

Я использую профессиональную визуальную студию 13. Является ли это ошибкой компилятора?

UPDATE Согласно комментарий, я исправил код там вместо

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

теперь у меня есть

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

это не дает мне правильный ответ, и сообщение об ошибке все еще всплывает.

Answer 1

Задача 1

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

a^b не используется для ^б в C++/

Проблема 2

Выбор междунар для LCM в течение 20 чисел, не может быть хороший выбор, поскольку он может переполняться.

Задача 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
2. LCM(a1, a2, a3, ... an) = LCM(a1, LCM(a2, a3, ... an))