整数因式分解的问题。了解了一下筛法计算素数的算法。之前都是直接跑的sqrt(n)...
上方的genPrime()即筛法。大致意思是开一个标识数组，通过循环，下标为合数的位置置为false。
#include<bits/stdc++.h>
using namespace std;
bool flag[]; //标志一个数是否为素数
int prime[]; //素数表,下标从0开始
int size=; //素数个数
void genPrime()
{
int max=;
memset(flag, true, sizeof(flag));//首先对标签数组进行初始化，全部设为true。
for(int i = ; i <= max / ; i++)
{
if(flag[i])
{
for(int j = i << ; j <= max; j += i)
{
flag[j] = false;
}
}
}
for(int i = ; i <= max; i++)
{
if(flag[i])
{
prime[size++] = i;//存储素数。将所有标志位依然为1的标志写入素数数组中去。
}
}
} int son[];
int j;
void breakNum(int num,int arr[])
{
for(int i=; i<sizeof(prime)/sizeof(int)&&prime[i]<=num;)
{
if(num%prime[i]==)
{
son[j]=prime[i];
j++;
num/=prime[i];
}
else
{
i++;
}
}
} int main()
{
memset(son,,sizeof(son));
genPrime();
int num;
cin>>num; if(num==)
{
cout<<<<endl;
}
else
{
breakNum(num,son);
for(int i=; i<j; i++)
{
if(son[i]!=)
{
if(i!=j-)
{
cout<<son[i]<<"*";
}
else
{
cout<<son[i]<<endl;
}
}
}
}
return ;
}