求正整数的质因数

算法描述

当给定一个正整数 $n$，求其质因数的算法可以描述如下：

1. 初始化一个变量 $i$ 为 2。
2. 如果 $n$ 能被 2 整除，则将 2 输出为一个质因数，并将 $n$ 除以 2。
3. 从 3 开始，使用一个循环逐个检查奇数 $i$ 是否是 $n$ 的质因数。
   • 如果 $n$ 能被 $i$ 整除，则将 $i$ 输出为一个质因数，并将 $n$ 除以 $i$。
   • 否则，增加 $i$ 的值，使其指向下一个奇数。
4. 如果 $n$ 大于 2，说明它本身就是一个质因数，将其输出。
5. 结束算法。

这个算法的基本思路是从最小的质数 $2$ 开始，逐个检查是否是 $n$ 的质因数。如果是，就将其输出，并将 $n$ 除以该质因数，继续检查下一个质数。通过循环和递增的方式，我们可以找到 $n$ 的所有质因数。

这个算法的时间复杂度取决于 $n$ 的大小和质因数的个数。在最坏情况下，时间复杂度为 $O(\sqrt{n})$。这是因为在循环中，我们从 $3$ 开始逐个检查奇数 $i$，直到 $i$ 的平方大于等于 $n$。

编程实现

#include <stdio.h>

void primeFactors(int n)
{
  while (n % 2 == 0)
  {
    printf("%d ", 2);
    n = n / 2;
  }
  for (int i = 3; i * i <= n; i = i + 2)
  {
    while (n % i == 0)
    {
      printf("%d ", i);
      n = n / i;
    }
  }
  if (n > 2)
  {
    printf("%d ", n);
  }
}

int main()
{
  int n;

  printf("请输入一个正整数：");
  scanf("%d", &n);

  printf("质因数为：");
  primeFactors(n);

  return 0;
}