为数的质因数找到更好的算法

Question

我接到了一项任务，要编写一个接受正整数并显示其质因数的程序。

我观察到，当给出大于 500000 的数字时，我的程序会花费大量时间来寻找质因数。

最后我失败了，因为当给出整数776621时，程序需要超过10秒来计算结果。我想了解如何优化我的代码，以便更快地给出结果。这是我的代码：

#include <stdio.h>
#include <stdlib.h>

int ft_isprime(int num)
{
    int i;
    int j;

    i = 0;
    j = 2;
    if (num <= 1 && num >= 0)
        return (0);
    if (num >= 2 && num <= 3)
        return (1);
    while (j < num)
    {
        if (num % j == 0)
            return (0);
        j++;
    }
    return (1);
}
int main(int argc, char **argv)
{
    int num;
    int divisor;
    int prime_divisors[30];
    int i;

    i = 0;
    num = 0;
    if (argc == 2)
        num = atoi(argv[1]);
    divisor = num;
    if (argc != 2)
    {
        printf("\n");
        return (0);
    }
    if (num == 1)
    {
        printf("1\n");
        return (0);
    }
    if (ft_isprime(num))
    {
        printf("%d\n", num);
        return (0);
    }
    while (num > 0 && divisor > 0)
    {
        if (ft_isprime(divisor))
        {
            if (num % divisor == 0)
            {
                num = num / divisor;
                prime_divisors[i] = divisor;
                i++;
                continue;
            }
        }
        divisor--;
    }
    while (i > 0)
    {
        if (i == 1)
            printf("%d", prime_divisors[i-1]);
        else
            printf("%d*", prime_divisors[i-1]);
        i--;
    }
    printf("\n");
    return (0);
}

输出示例：

$> ./fprime 225225 | cat -e
3*3*5*5*7*11*13$
$> ./fprime 8333325 | cat -e
3*3*5*5*7*11*13*37$
$> ./fprime 9539 | cat -e
9539$
$> ./fprime 804577 | cat -e
804577$
$> ./fprime 42 | cat -e
2*3*7$
$> ./fprime 1 | cat -e
1$
$> ./fprime | cat -e
$
$> ./fprime 42 21 | cat -e
$

Answer 1

这是一个运行速度稍快的实现：

#include <vector>

using namespace std;

bool isPrime(int n) {
  if (n == 1) {
    return false;
  }

  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }

  return true;
}

vector<int> getPrimeFactors(int n) {
  if (n == 1) {
    return vector<int>();
  } else if (isPrime(n)) {
    return vector<int>(1, n);
  }

  vector<int> primeFactors;
  while(n > 1) {
    // find next factor
    int factor = 2;
    for (factor = 2; factor <= sqrt(n); factor++) {
      if (n % factor == 0) {
        break;
      }
    }

    // remove as many factors as possible
    while (n % factor == 0 && n > 1) {
      n /= factor;
      primeFactors.push_back(factor);
    }

    if (isPrime(n)) {
      primeFactors.push_back(n);
      n = 0;
    }
  }

  return primeFactors;
}

为数的质因数找到更好的算法

Find a better algorithm for prime factors of a number

c

algorithm

gcc

primes

prime-factoring