最大プライムファクタ - C++

Question

私は、数字600851475143の最大の素因数を見つけようとしています。しかし、600851475143に直面すると、4370432が返されます。間違いなくプライムではありません。私のコードで何が間違っているのでしょうか？

#include <iostream> 
#include <time.h> 
#include <math.h> 

using namespace std; 

int main() 
{ 

int num; 
int largest; 
int count; 

cout<<"Please enter a number to have its Largest Prime Factor found"<<endl; 
cin>>num; 
num = 600851475143; 

for (int factor = 1; factor <= num; factor++) 
{ 
    if (num % factor == 0) 
    { 
     count = 0; 
     for (int primetest=2; count == 0 && factor > primetest ; primetest++) 
     { 
      if (factor % primetest == 0) 
      count ++;  
      //endif 
     } 
     if (count == 0) 
     largest = factor; 
     //endif 
    }  

}//endif 
cout<<largest<<endl; 
system("PAUSE"); 
} 

Answer 1

num = 600851475143; 

整数オーバーフローがここに発生します。 numのサイズは、指定した値を格納するのに十分な大きさではありません。

uint64_tを使用してください。

#include <cstdint> //must include this! 

uint64_t num = 600851475143; 

この読み：cstdint

Answer 2

をと訂正を提供します。あなたのコンパイラに応じて、unsigned longを試して、それがあなたの答えを保持できるかどうかを見ることができます。試して、coutに書き込んで、変数が期待する値を保持しているかどうかを確認してください。

最大の因子を見つけようとすると、考えられる最も高い要素から数えて効率的になることはありませんか？

Answer 3

コードには大きな問題がいくつかありますので、より完全な ソリューションを示したいと思います。主な問題は、入力検証がないことです！良いコードは正しく入力する必要があります。 すべての入力に拒否されません。そこで私は現在、 入力の適切な読み込みと検証を含んでいます。このようにして、自動的に問題を捉えました。

すべての主要なタイプに固有の名前が必要です。だから私はtypedefのuint_typeを導入しました。 コンパイラは、入力60085147514が であるかどうかをコンパイル時にも知ることができます（これは実行時にも拒否されますが）。コンパイラが警告する場合は、 より大きな整数型を使用する必要があります。しかし、すべての共通の 64ビットプラットフォーム（しかし、共通の32ビットプラットフォームではない）では、unsigned longで十分です。より大きい整数型が必要な場合は、 に変更する必要があります。

あなたのアルゴリズムはひどく非効率です！必要なのは、数字をすべて に分割して（可能な限り）、素数 にしか遭遇しないことが保証されているため、そのことを確認する必要はありません。また、入力の平方根である までの因子を考慮する必要があります。これはすべて考え抜くために少しの論理を必要とします - コードを参照してください。

あなたのコードはローカリティの原則に違反しています： が必要な場所に変数を宣言してください。また、非C++ヘッダーも含まれていました。さらに、 は必要ありませんでした。 usingディレクティブを使用すると、コードがわかりにくくなります。つまり、コンポーネントがどこから来たのかはもうわかりません。 それらのための必要はありません！私はまた、より顕著な定義のために 匿名名前空間を導入しました。

最後に、私は2つのスペースで、よりコンパクトなコーディングスタイル（インデントを使用し、可能な場合はブラケットを避けそれについて考え 同じライン上のブラケットは、：。このように、あなたは一方で、一目でずっと 多くを見ることができます少しの訓練でそれを読むのも簡単です。

図のようにコンパイルすると、コンパイラはlargest_factorについて警告し、おそらくundefinedを使用します。 これは当てはまりませんので、私はここで警告を空とみなすことにしました。

Program LargestPrimeFactor.cpp: 
// Compile with 
// g++ -O3 -Wall -std=c++98 -pedantic -o LargestPrimeFactor LargestPrimeFactor.cpp 

#include <string> 
#include <iostream> 

namespace { 
    const std::string program_name = "LargestPrimeFactor"; 
    const std::string error_output = "ERROR[" + program_name + "]: "; 
    const std::string version_number = "0.1"; 

    enum ErrorCodes { reading_error = 1, range_error = 2 }; 
    typedef unsigned long uint_type; 
    const uint_type example = 600851475143; // compile-time warnings will show 
    // whether uint_type is sufficient 
} 

int main() { 

    uint_type number; 
    std::cout << "Please enter a number to have its largest prime factor found:" 
    << std::endl; 
    std::cin >> number; 
    if (not std::cin) { 
    std::cerr << error_output << "Number not of the required unsigned integer" 
    " type.\n"; 
    return reading_error; 
    } 
    if (number <= 1) { 
    std::cerr << error_output << "Number " << number << " has no largest prime" 
    " factor.\n"; 
    return range_error; 
    } 
    const uint_type input = number; 

    uint_type largest_factor; 
    for (uint_type factor = 2; factor <= number/factor; ++factor) 
    if (number % factor == 0) { 
     largest_factor = factor; 
     do number /= factor; while (number % factor == 0); 
    } 
    if (number != 1) largest_factor = number; 

    std::cout << "The largest prime factor of " << input << " is " << largest_factor 
    << ".\n"; 
} 

Answer 4

あなたは長い長いint型としてあなたNUM変数を宣言することができます。

long long int num; 

これにより、コードで発生するすべてのタイプのオーバーフローが回避されます。