2016-08-19 6 views
0

次の数式を使用して数値のLCMを検索しようとしています。 Lcm = Gcd /(a * b)である。これは少数では問題なく動作していますが、コードに表示されているように、数値が大きいほどオーバーフローします。私はlong型を可変型として使用しようとしましたが、効果はありません。オーバーフローの問題を解決するにはどうすればよいですか?大きい値の場合はオーバーフローします

#include <iostream> 
#include <vector> 
using namespace std; 

long long int LCM(int n1, int n2){ 

    const int size = 2; 
    long long int sum; 
    long long int gcd; 
    long long int lcm = 0; 
    vector<int> number(2); 
    number[0] = n1; 
    number[1] = n2; 

while (true) 
{ 
    sum = number[0] % number[1]; 
    gcd = number[1]; 
    if (sum == 0) 
     break; 
    number[0] = number[1]; 
    number[1] = sum; 
} 

lcm = ((n1*n2)/gcd); 
return lcm; 
} 

int main() 
{ 

    cout << LCM(28851538, 1183019) << endl; 
    system("pause"); 

} 
+1

n2の使用N1/GCD *そして、あなたの質問は何ですか? – dhke

+0

それはあふれている。どのように私はそれを修正するのですか? –

+0

もっと大きなデータ型を使うことで、例えば 'unsigned long long'やGMPやBoostを見てください – Rakete1111

答えて

4

些細な改善があります。

あなたは(n1 * n2)/ gcdを計算します。 n1 * n2が大きすぎてintに収まらない場合は、オーバーフローします。 1つの明らかな変更は、(長いlong)n1 *(長いlong)n2)/ gcdを計算することです。 n1 * n2が長すぎる長さに収まるには大きすぎない限り、それは問題ありません。

しかし、この関数を長いlong引数で使用したいとします。そして、gcdはn1とn2の最大公約数であることを忘れないでください。それはn1の除数とn2の除数です。したがって、(n1/gcd)* n2または(n2/gcd)* n1を計算すると、同じ結果が得られます。最終的な結果が大きすぎない限り、オーバーフローは発生しません。

lcm = n1*(n2/gcd); 
2

にreturn文を変更!

vector<int> number(2) 

なぜint?

lcm = ((n1*n2)/gcd) 

0
long long int LCM(int n1, int n2) 

パラメータはint型です:あなたはgcdが均等に両方の数に分割し、単に操作の順序を変更することを知っているので

だから

return (n1/gcd) * n2; 
関連する問題