1059. Prime Factors (25)

1059. Prime Factors (25)

时间限制

50 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

HE, Qinming

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p₁^k₁* p₂^k₂ *…*p_m^k_m.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p₁^k₁ * p₂^k₂ *…*p_m^k_m, where p_i's are prime factors of N in increasing order, and the exponent k_i is the number of p_i -- hence when there is only one p_i, k_i is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

这题和之前的一题很像。http://xujiayu317.blog.163.com/blog/static/2547520920149218497214/

但是这题过程中一直有个结果错误。看了那些ac的代码。发现是要当num=1时要1=1  改了一下就过了（但是1不是质数吧，这属于特殊条件）。

评测结果

测试点

#include<iostream>
#include<math.h>
using namespace std;
class PrimeFactors
{
private:
  long int e,m;
  PrimeFactors* next;
public: 
  void printpf();
  void line(long int ee,long int mm);
  PrimeFactors*head,*sail;
  PrimeFactors()
  {
   head=NULL;
   sail=NULL;
  }
};
void PrimeFactors::printpf()
{   
 cout<<head->e<<"=";
 sail=head;
 head=head->next;
 delete sail;
 while(head->next)
 {
  cout<<head->e;
  if(head->m!=1)
  {
   cout<<"^"<<head->m;
  }
  cout<<"*";sail=head;
      head=head->next;
     delete sail;
 } 
     cout<<head->e;
  if(head->m!=1)
  {
   cout<<"^"<<head->m;
  }
  delete head;
  cout<<endl; 
  head=NULL;
  sail=NULL;
}
void PrimeFactors::line(long int ee,long int mm)
{
 PrimeFactors*p;
 if(head)
 {
  p=new PrimeFactors;
  p->e=ee;
  p->m=mm;
  sail->next=p;
  sail=p;
 }
 else
 {
    head=new PrimeFactors;
    head->e=ee;
    head->m=0;
    sail=head;
 }
 sail->next=NULL;
}
int main()
{
 PrimeFactors pf;
 long int num,add,count;
    cin>>num;
  if(num>1)
  {
 pf.line(num,0);
    add=2;
 count=0; 
 while(num%add==0)
 {
    num/=add;
       count++;
 } 
 if(count!=0)
 {
  pf.line(add,count);
 }
 add=3;
 while(num>2&&add<=sqrt(num))
 {
  count=0;
  while(num%add==0)
  {
   count++;
   num/=add;
  }
  if(count!=0)
  {
   pf.line(add,count);
  }
  add+=2;
 } 
 if(num>2)
   pf.line(num,1);
   pf.printpf();
}
  else cout<<num<<"="<<num<<endl;
 return 0;
}