辅导笔记(4):质因数分解

// 把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

//输入样例：36

//输出：36=2*2*3*3

#include<iostream>

#define N 101

using namespace std;

int a[N],b[N];

bool isprime(int x){

for(int i=2;i*i<=x;i++){

if(x%i==0) {

return false;

break;

}

}

return true;

}

int main()

{

int n;

cin>>n;

int s=1,j=1;//s表示累积

if(n<2||n/2!=0) cout<<"n不是合数!"<<endl;

for(int i=2;i<=n;i++)

  if(isprime(i))

  {

  a[j]=i;

  j++;

  }

//  测试是否找出了全部可能的质数因子 

// for(int i=1;i<n;i++)

//   if(a[i]!=0)

//   cout<<a[i]<<' ';

    int i=1,k=1;

int m=n;

while(s!=n){

if(m%a[i]==0&&m!=0)

  {

  b[k]=a[i];

  s=s*b[k];

  k++;

  m=m/a[i];

  }

else  i++;

}

  cout<<n<<"="<<b[1];

  for(int i=2;i<k;i++)

  if(b[i]!=0)

  cout<<'*'<<b[i];

return 0;

}