算数基本定理：

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3……Pnan，这里P1<P2<P3……<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。最早证明是由欧几里得给出的，现代是由陈述证明。此定理可推广至更一般的交换代数和代数数论。
取自百度百科
简而言之就是任何一个整数都可以用有限个质数来表示。
今天就遇到一道题：分解素因子。
原题如下：

看到这题表示自己没什么思路，于是百度看了下别人的代码，大概有了点思路。

#include <stdio.h>
#include <math.h>
int isprime(int n)  //判断一个数是不是质数（素数），是返回1，不是返回0
{
  int t = sqrt(n);
  for (int i = 2; i <= t; ++i)
  {
    if (n%i == 0)
    {
      return 0;
    }
  }
  return 1;
}
int main()
{
  int k;
  int n;
  int c = 0;
  scanf("%d", &k);
  int sum[50] = { 0 };
  while (k != 1)
  {
    scanf("%d", &n);
    for (int i = 2; i <= n;) //处理前面k-1个数
    {
      if (n%i == 0 && isprime(i))
      {
        sum[c] = i;
        n /= i;
        c++;
      }
      else
        ++i;
    }
    for (int i = 0; i < c - 1; i++)
    {
      printf("%d*", sum[i]);
    }
    printf("%d\n", sum[c - 1]);
    c = 0;
    k--;
  }
  scanf("%d", &n);
  for (int i = 2; i <= n;)   处理第k个
  {
    if (n%i == 0 && isprime(i))
    {
      sum[c] = i;
      n /= i;
      c++;
    }
    else
      ++i;
  }
  for (int i = 0; i < c - 1; i++)
  {
    printf("%d*", sum[i]);
  }
  printf("%d\n", sum[c - 1]);
  return 0;
}

提交以为能ac，结果被”Time Limit Exceed on test 1“打脸。
继续探索中。
————————–分隔————————–
2018.10.25 22：37 成功AC 还是找了学长，学长给了思路，要我打表提高效率，并且给出了更好的方法无奈还没理解。
/*
与上一个最大的区别再于打表，并且用打表的数来直接当作素因子，而不用一个一个重新去判断是否为素数
*/

//变量有点多，有点杂
#include <stdio.h>
#include <math.h>
int main()
{
  int prime[6542] = { 0 };    //经实验，65535中共有质数6541个  
  prime[0] = 2;
  prime[1] = 3;
  int j = 2;
  int k = 0;
  int n = 0;
  int c = 0;
  for (int i = 5; i <= 65535; i+=2)   //打表 2-65535的质数
  {
    int t = sqrt(i);
    for (int k = 2; k <= t; k++)
    {
      if (i%k != 0)
      {
        if (k == t)
        {
          prime[j] = i;
          j++;
        }
      }
      else
        break;
    }
  }
  scanf("%d", &k);
  int sum[65535] = { 0 };
  while (k != 1)    //基本与前面相同
  {
    scanf("%d", &n);
    for (int i = 0; prime[i] <= n;)   //基本上是把i改成了prime[i],下同，减少了判断的次数
    {
      if (n%prime[i] == 0)
      {
        sum[c] = prime[i];
        n /= prime[i];
        c++;
      }
      else
        ++i;
    }
    for (int i = 0; i < c - 1; i++)
    {
      printf("%d*", sum[i]);
    }
    printf("%d\n", sum[c - 1]);
    c = 0;
    k--;
  }
  scanf("%d", &n);
  for (int i = 0; prime[i] <= n;)
  {
    if (n%prime[i] == 0)
    {
      sum[c] = prime[i];
      n /= prime[i];
      c++;
    }
    else
      ++i;
  }
  for (int i = 0; i < c - 1; i++)
  {
    printf("%d*", sum[i]);
  }
  printf("%d", sum[c - 1]);
        return 0;
}

继续探索（学长说的更好的打表方法）。。