問題 E: 因式分解

時間限制: 1 Sec  

記憶體限制: 64 MB

送出: 47  

解決: 32

[

​​送出​​][

​​狀态​​][

​​讨論版​​]

題目描述

将大于1的自然數N進行因式分解,滿足N=a1*a2*a3…*am。 

編一程式，對任意的自然數N（1<N<=2,000,000,000），求N的所有形式不同的因式分解方案總數。如N=12，共有8種分解方案，他們分别是： 

12=12 

12=6*2 

12=4*3 

12=3*4 

12=3*2*2 

12=2*6 

12=2*3*2 

12=2*2*3

輸入

輸入隻有一行，一個整數N

輸出

輸出隻有一行，一個整數表示自然數N的因式分解方案總數

樣例輸入

12      

樣例輸出

8      

今早的簽到題，用N除以2一直到N，結果不為整則加1再除；

若為整，用商代替N，從2開始除一直到N。

很簡單的遞歸函數。

#include <stdio.h>
int sum=1;
void fx(int n)
{
    int i;
    for(i=2; i<n; i++)
    {
        if(n%i==0)
        {
            fx(n/i);
            sum++;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    fx(n);
    printf("%d\n",sum);
    return 0;
}