【1059】Prime Factors (25 分)

简介: 【1059】Prime Factors (25 分)【1059】Prime Factors (25 分)
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std; 
//举例:97532468=2^2*11*17*101*1291
const int maxn=100010;
bool is_prime(int n){ //判断n是否为素数
  if(n==1) return false;
  int sqr =(int)sqrt(1.0*n);
  for(int i=2;i<=sqr;i++){
    if(n%i == 0)  return false;
  }
  return true;
}
int prime[maxn] ,pNum=0;
void Find_Prime(){  //求素数表
  for(int i=1;i<maxn;i++){
    if(is_prime(i) == true){
      prime[pNum++]=i;
    }
  }
}
struct factor{
  int x,cnt; //x为质因子,cnt为其个数
}fac[10];
int main(){   
  Find_Prime(); //此句请务必要记得写
  int n,num=0; //num为n的不同质因子的个数
  scanf("%d",&n);
  if(n==1)  printf("1=1");  //特判1的情况
  else{
    printf("%d=",n);
    int sqr=(int)sqrt(1.0*n); //n的根号
    //枚举n以内的质因子
    for(int i=0;i<pNum && prime[i] <=sqr;i++){
      if(n % prime[i] == 0) { //如果prime[i]是n的因子
        fac[num].x=prime[i]; //记录该因子
        fac[num].cnt=0;
        while(n % prime[i]==0) { //计算出质因子prime[i]的个数
          fac[num].cnt++;
          n/=prime[i];
        }
        num++;//不同质因子个数加1
      }
      if(n == 1)  break;//及时退出,节省点时间
    }
    if(n != 1){ //如果无法被根号n以内的质因子除尽
      fac[num].x=n;  //那么一定有一个大于根号n的质因子
      fac[num++].cnt=1;
    }
    //按格式输出结果
    for(int i=0;i<num;i++){
      if(i>0)  printf("*");
      printf("%d",fac[i].x);
      if(fac[i].cnt > 1){
        printf("^%d",fac[i].cnt);
      }
    }
  }
  system("pause");
    return 0;   
}
相关文章
|
机器学习/深度学习 C++
【PAT甲级 - C++题解】1059 Prime Factors
【PAT甲级 - C++题解】1059 Prime Factors
78 0
|
网络架构
Codeforces Round #755 D. Guess the Permutation(交互 二分)
Codeforces Round #755 D. Guess the Permutation(交互 二分)
90 0
|
人工智能 BI
CodeForces - 1485D Multiples and Power Differences (构造+lcm)
CodeForces - 1485D Multiples and Power Differences (构造+lcm)
82 0
【欧拉计划第 5 题】最小公倍数 Smallest multiple
【欧拉计划第 5 题】最小公倍数 Smallest multiple
156 0
【欧拉计划第 5 题】最小公倍数 Smallest multiple
【欧拉计划第 3 题】最大质因数 Largest prime factor
【欧拉计划第 3 题】最大质因数 Largest prime factor
258 0
【1142】Maximal Clique (25分)【有点问题】
【1142】Maximal Clique (25分)【有点问题】 【1142】Maximal Clique (25分)【有点问题】
80 0
|
人工智能
HDOJ/HDU 2710 Max Factor(素数快速筛选~)
HDOJ/HDU 2710 Max Factor(素数快速筛选~)
104 0
【1096】Consecutive Factors (20 分)
【1096】Consecutive Factors (20 分) 【1096】Consecutive Factors (20 分)
124 0
HDOJ(HDU) 2136 Largest prime factor(素数筛选)
HDOJ(HDU) 2136 Largest prime factor(素数筛选)
108 0
【1046】Shortest Distance (20 分)
【1046】Shortest Distance (20 分) 【1046】Shortest Distance (20 分)
91 0