Prime Factorization
分解质因数算法
分解质因数就是将一个整数n如90，分解成90 = 2 * 3 * 3 * 5；
算法步骤
首先找出最小的质因数，如果这个质因数是自己，那么n只有一个质因数即自己
然后当n != k时，如果n能整除k那么k就是n的一个质因数
如果不能整除那么k += 1，并继续
非递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
int i,n;
std::cin>>n;
for(i=2;i<=n;i++)
{
while(n!=i) //若i=n，则质因数就是n本身
{
if(n%i==0) //若i是质因数，则打印出i的值，并用商给n赋新值
{
std::cout<<i;
n=n/i;
}
else break;//若不能被i整除，则算下一个i
}
}
std::cout<<n; //这里是打印最后一个质因数，也就是等于i时的那个
return 0;
}
递归版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void PrimeFactor(int n)
{
if (n > 1)
{
int prime = 0;
for (int i = 2; i <= n; ++i)
{
if (n % i == 0)
{
prime = i;
break;
}
}
if (prime != 0)
{
PrimeFactor(n / prime);
cout << prime << endl;
}
else
cout << n;
}
}
时间复杂度：
- 最坏情况下 n
- 一般情况下logn