0

我试图找到数字 600851475143 的最大素数。我的代码适用于我测试的较小数字(低于 100)。但是,当遇到 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");
}
4

4 回答 4

4
num = 600851475143;

这里发生整数溢出。的大小num不足以包含您提供的值。

使用uint64_t.

#include <cstdint>  //must include this!

uint64_t num = 600851475143;

阅读:cstdint

于 2011-08-15T07:11:38.477 回答
4

代码存在不少大问题,所以我想展示一个更好的完整解决方案。主要问题是它没有输入验证!好的代码必须在它不拒绝的所有输入上都是正确的。所以我现在已经包括正确阅读和验证输入。这样,您就会自动发现问题。

所有主要类型都需要有专有名称!所以我介绍了typedef uint_type。如果输入 60085147514 有效或无效(尽管现在在运行时也被拒绝),编译器也会在编译时发现。如果编译器发出警告,那么您需要使用更大的整数类型;但是 unsigned long 在所有常见的 64 位平台上就足够了(但不是在常见的 32 位平台上)。如果您需要更大的整数类型,那么现在只需更改一处。

你的算法效率太低了!所需要的只是将数字除以找到的所有因子(尽可能长),并且保证您只会遇到素数 - 因此无需检查。而且只需要考虑输入平方根的因素。这一切都需要一些逻辑来思考——看代码。

那么你的代码就违反了局部性原则:在需要它们的地方声明你的变量,而不是在其他地方。您还包括了非 C++ 头文件,这些头文件也不需要。using-directives 的使用只是混淆了代码:你看不到组件来自哪里;并且不需要它们!我还介绍了一个匿名命名空间,用于更突出的定义。

最后,我使用了更紧凑的编码风格(缩进 2 个空格,括号在同一行,尽可能避免使用括号。想一想:这样你可以一眼看到更多内容,同时稍加训练也更容易阅读。

如图所示编译时,编译器警告最大的因子可能未定义。情况并非如此,我在这里选择将该警告视为空的。

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";
}
于 2011-08-15T09:58:48.820 回答
0

并提供更正。根据您的编译器,您可以尝试 unsigned long 并查看是否可以保留您的答案。尝试写入 cout 并查看变量是否保持您期望的值。

另一方面,如果您试图找到最大的因素,从可能的最高因素开始倒数不是更有效吗?

于 2011-08-15T07:20:52.013 回答
0

您可以将num变量声明为long long int

long long int num;

这将避免代码中发生的所有类型的溢出!

于 2017-11-29T09:21:32.943 回答