【算法】简单质因数分解

C语言代码

/*质因数分解*/
#include<iostream>
using namespace std;

bool Judge(int x)
{
int s=0;
for(int i=2;i<x;i++)
{
if(x%i==0)
s++;
}
if(s==0)
return true;
else
return false;
}

int main()
{
while(true)
{
float n_substitute,n;
int s=1,k=0;
cin>>n;
n_substitute=n;

cout<<n<<"=";

for(int i=2;s!=n_substitute;)
{
if(int(n)%i==0&&Judge(i))
{
if(k!=0)
{
cout<<"*"<<i;
n/=i;
s*=i;
}
if(k==0)
{
cout<<i;
n/=i;
s*=i;
k++;
}
}
if(int(n)%i!=0)
i++;
}
cout<<endl;
}
return 0;
}

---

• 任何一个大于1的整数都能被分解几个素数的乘积
• Judge()子函数为bool类型的质数判断函数
• 从2开始判断是否为素数。循环结束的条件为素数乘积是否等于该整数。
• 倘若该素数不能再次被该整数整除，那么i++
• 每找到一个素数因子，需要用该整数去整除该因子，避免陷入死循环