分解质因数

    根据数论的知识可知任何一个合数都可以分解写成几个质数相乘的形式，编写程序对一个数进行分解质因数。

    我们知道一个合数n,可以在2~n-1之间找到两个因数i,j使i*j=n;如果i是质数，则i一定是n的一个质因数，否则继续对i进行分解质因数；同理，如果j是质数，则j一定是n的一个质因数，否则继续对j进行分解质因数。因此是个递归的过程，根据上述思想，编写代码如下：

#include <stdio.h>

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

void PrimeFactor(int n)
{
  int i;
  if(isPrime(n))
    printf("%d ",n);
  else
  {
    for(i=2; i<n; i++)
      if(n % i == 0)
      {
        printf("%d ",i);
        if(isPrime(n/i))
        {
          printf("%d ",n/i);
        }
        else
        {
          PrimeFactor(n/i);
        }
        break;
      }
  }
}

int main(int argc, char *argv[])
{
  int n;
  printf("please input a integer for getting prime factor\n");
  scanf("%d",&n);
  PrimeFactor(n);
  printf("\n");

  return 0;
}

程序执行结果：

please input a integer for getting prime factor

1000

2 2 2 5 5 5