首页 文章

最大的素数因子-C

提问于
浏览 次
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");
}
c++ prime-factoring

4 回答

  • 4
    num = 600851475143;

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

    使用 uint64_t .

    #include <cstdint>  //must include this!

uint64_t num = 600851475143;

    阅读本文：cstdint

    回复于
  • 0

    代码有很多主要问题，所以我想展示一个更好的完整解决方案 . 主要问题是它没有输入验证！好的代码必须在它不拒绝的所有输入上都是正确的 . 所以我现在已经包含了适当的阅读和输入验证 . 通过这种方式，您可以自动发现问题 .

    所有主要类型都需要有专有名称！所以我介绍了typedef uint_type . 如果输入60085147514有效，编译器也会在编译时发现（尽管现在也在运行时被拒绝） . 如果编译器发出警告，那么你需要使用更大的整数类型;但是，在所有常见的64位平台上，无符号长度就足够了（但在普通的32位平台上却没有） . 如果您需要更大的整数类型，那么现在只需要更改一个地方 .

    你的算法非常低效！所需要的只是将数字除以找到的所有因子（尽可能长），并且保证只能遇到素数 - 所以不需要检查它 . 并且还需要考虑直到输入的平方根的因子 . 这一切都需要一些逻辑思考 - 参见代码 .

    然后你的代码违反了局部性原则：将变量声明在需要的地方，而不是其他地方 . 您还包括非C标头，此外不需要 . use-directives的使用只会混淆代码：你不再看到组件的来源;而且没有必要！我还介绍了一个匿名命名空间，用于更突出的定义 .

    最后，我使用更紧凑的编码风格（2个空格缩进，同一行上的括号，尽可能避免使用括号 . 想一想：通过这种方式，您可以一目了然地看到更多，同时进行一些培训也更容易阅读 .

    当如图所示编译时，编译器警告可能使用undefined的largest_factor . 事实并非如此，我选择将此警告视为空白 .

    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";
}
    回复于
  • 0

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

    另一方面，如果你试图找到最大因素，那么从最高可能因素倒数就不是更有效率吗？

    回复于
  • 4

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

    long long int num;

    这样可以避免代码中出现所有类型的溢出！

    回复于

相关问题