蓝桥杯算法提高VIP-计算质因子 （C语言描述，注释详细）

解题思路:

                1.首先找到从1-10000的所有质数，由大到小存放在数组a中

                2.输入数n之后，判断n是否是质数，是就直接输出

                3.否则在数组a里n的质因子，从小到大输出

注意事项:

                1.质因子不要重复输出，每个质因子只输出一次，比如 300 输出 2 3 5

参考代码:

#include <stdio.h>

#include <string.h>

int a[10001];//a数组用来存放1-10000由大到小的所有质数 

int zhishu(int shu)//判断质数的函数 

{

 int i;

 for(i = 2; i < shu; i++)

 {

  if(shu % i == 0)

   return 0;

 }

 return 1;

}

int main()

{

 int n,i;

 int count = 1;//用来计算3-10000的所有质数 

 memset(a,0,sizeof(a));//数组赋初值0 

 scanf("%d",&n);

 a[0] = 2;//2是特殊的质数，直接存入a[0] 

 for(i = 3; i <= 10000; i++)

 {

  if(zhishu(i))

  {

   a[count++] = i;//用来存2-10000的所有质数 顺序是从大到小 

  }

 }

 if(zhishu(n))//如果是素数就直接输出 

 {

  printf("%d",n);

 }

 else

 {

  for(i = 0; i <= count; i++)

  {

   if(n == 1)//n除尽了就跳出for循环 

    break;

   if(n % a[i]== 0)//找到了一个符合条件的质因子 

    {

     printf("%d ",a[i]);/*！注意质因子只输出一次！*/

     while(n % a[i] == 0) 

     {

      n = n / a[i];//一直累除同一个质数，直到不能除尽位置 

     }

    

    }

   }

 }

 return 0;

}