c - 欧拉计划挑战 3

Question

我的代码有问题，我不知道是什么。GCC 编译它时没有任何警告，但运行时没有任何输出。

我只是在学习c（这实际上是欧拉的问题3。找到600851475143的最大素数）。

这段代码有什么问题？

#include <stdio.h>

int primeCheck(unsigned long input);

int main(){
  //goal: find largest prime factor of 600851475143
  unsigned long goal = 600851475143;
  for(unsigned long i = 600851475142; i > 0; i--){
    if(primeCheck(i) == 1 && goal%i == 0)
      printf("\n%lu\n\n", i);
  }

}

int primeCheck(unsigned long input){
  for(unsigned long i = 2; i < input; i++){
    if(input%i == 0)
      return 0;
  }
  return 1;
}

Answer 1

假设您使用的是正确大小的数据结构（对此已经进行了足够多的讨论），那么您的程序肯定需要很长时间才能执行。

请注意，除非 600851475143 本身是质数，否则最大的质因数不能超过 1/3（我们可以清楚地看到 2 肯定不是一个因数）。这就是说，几乎没有数学，我已经可以告诉你，第一个 for 循环中的 if 语句将返回 false 超过 4000 亿次，并且你正在对它们中的每一个进行素数检查。我不在乎你使用什么算法；您无法快速进行 4000 亿次素数检查。即使你交换它以利用短路，你也在做 4000 亿次可分性检查，这也没有效率。

由于这是欧拉计划，我不会放弃它，但我会给出一个提示：假设你知道一些较小的素因数。您如何使用它来设定最大因素的上限？

Answer 2

您的程序很可能执行时间过长。按照 Jerry 的提示尝试更小的数字来验证您的程序。

您可能想看看这篇文章：大数的素数分解以获得更好的算法。

Answer 3

OP 的代码适用于 64-bit unsigned long，但耗时太长。

问题：

primeCheck()迭代最多i < input而不是最多i <= isqrt(input). 两者都可以工作，但只要达到 的平方根input，代码就会更快地完成。不需要进一步测试。

通常，余数和商是一起计算的，因此通过对商进行测试，代码可以免费获得“大约平方根”——除数何时变得小于商？

int primeCheck(unsigned long input){
  unsigned long q = input;
  // for(unsigned long i = 2; i < input; i++){
  for(unsigned long i = 2; i <= q; i++){
    if(input%i == 0) {
      return 0;
    }
    q = input/i;
  }
  return 1;
}

主循环开始寻找仅比目标少 1 的因子。这将起作用，但第一个可能的因素是isqrt(goal). 这要快得多

int main() {
  //goal: find largest prime factor of 600851475143
  unsigned long long goal = 600851475143;
  unsigned long goal_sqroot = (unsigned long) sqrt(goal);

  // In case  `double sqrt(double)` gave a too low `isqrt()` answer ...
  if (goal/goal_sqroot > goal_sqroot) goal_sqroot = goal/goal_sqroot;

  // for(unsigned long i = 600851475142; i > 0; i--){
  for (unsigned long long i = goal_sqroot; i > 1; i--) {
    if (primeCheck(i) == 1 && goal % i == 0)
      printf("%llu\n", i);
  }
}

unsigned long可能只有 32 位。用于unsigned long long较大的数字，例如 600851475143，一个 40 位的数字。

< 2 秒内输出：

6857
1471
839
71

其他可能的简化，这是一个开始。