PAT：1059. Prime Factors (25) AC

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAX=100010;      //int型素数一定在这个范围内

int PrimeArr[MAX];        //素数表
int cnt=0;            //素数表中素数个数
int x,x2;            //输入的数字，x2是x的开平方数，x的因子只有从2到根号x+1

struct factor
{
  int num,amount;        //num代表这个结构代表的素数，amount代表这个素数的个数
}fac[10];            //【skill】2*3*5*7*11*13*17*19*23*29已超出int范围了，10个结构就足够了
int facI=0;            //fac的下标

bool isPrime(int a)        //判断是否为素数
{
  if(a==1)
    return 0;
  else
  {
    int sqr=sqrt(a*1.0);
    for(int i=2 ; i<sqr+1 ; ++i)
      if(a%i==0)
        return 0;
  }
  return 1;
}

void Prinmetable()          //生成素数表
{
  for(int i=2 ; i<MAX ; ++i)
    if(isPrime(i)==1)
      PrimeArr[cnt++]=i;    //是素数，存入素数表
}

int main()
{
  memset(fac,0,sizeof(fac));
  scanf("%d",&x);
  printf("%d=",x);        //后面x要改变，这里就先将x输出
  if(1==x)            //特判1，既不是素数也不是合数
  {
    printf("1");
    return 0;
  }
  x2=sqrt(1.0*x);          //【skill】x的开平方数，x的因子只有从2到根号x+1
  Prinmetable();          //生成素数表
  //情况1：x不是素数
  for(int i=0 ; i<cnt && x2>=PrimeArr[i]; ++i)  //统计素数;【caution】x>=PrimeArr[i]必须加上，PrimeArr[i]>x2即大于x的开平方一定没有约数了
  {
    int su=PrimeArr[i];
    if(x%su==0)              //说明是因子
    {
      fac[facI].num=PrimeArr[i];
      while(x%su==0)          //统计该因子个数
      {
        ++fac[facI].amount;
        x/=su;
      }
      ++facI;
    }
    if(1==x)
      break;
  }
  //情况2：x本身就是单独的素数
  if(1!=x)
  {
    ++fac[facI].amount;      //【warning】顺序不能颠倒，不然导致数量加到下一个上
    fac[facI++].num=x;
  }
  for(int i=0 ; i<facI ; ++i)    //输出
  {
    int tmp=fac[i].amount;
    if(tmp!=0)
    {
      if(tmp>=2)
        printf("%d^%d",fac[i].num,tmp);
      else
        printf("%d",fac[i]);
      if(i!=facI-1)      //控制“*”的输出量
        printf("*");
    }
  }
  system("pause");
  return 0;
}

PAT：1059. Prime Factors (25) AC

原文：http://www.cnblogs.com/Evence/p/4314737.html