後面第4點“解決思路”說了什麽？

先做一點定性分析吧：題目指輸入的N是long int型的，在16位機器上，這通常是32位整數，對分解質因數而言，考慮正負號是沒什麽意義的，所以一般取unsigned型，這個數據類型的範圍是4G，考慮最極端的可能，輸入的N恰好是最大的那個素數，那個判斷是否素數的算法要循環多少次？又再假如，輸入的N其質因數有許多（32位以内65535的素數達3000多個），哪怕這個N由100個素數相乘，該如何操作遞歸？玩數學的可能會有某些現成定理可資利用，但我不知道，所以想先看看那書上的“解決思路”是什麽。

我后来看了书上的解析改了一下还是不行。书上就是要拿这题练习递归啊

反正闲着也闲着，就按你题意做了个，运行效果及代码如下：

#include<stdio.h>
void ff(int n,int a[],int l)
{//分解质因数，质因数都存储在数组a中
    int i;
    for(i=2;(i*i<=n)&&(n%i);i++);
    if(i==1||i*i>n)a[l]=n;
    else
    {
        a[l]=i;
        ff(n/i,a,++l);
    }
}
int main()
{
    int i,j,k,n,a[100]={0};
    printf("输入需分解的数(任意字符退出):");
    while(scanf("%d",&n))
    {
        for(i=0;i<100;i++)a[i]=0;
        ff(n,a,0);
        printf("%d=",n);
        for(i=0,j=0,k=1;i<100;i++)
        {
            if(a[i]!=j)
            {
                if(j&&k>1)printf("^%d",k);
                if(i&&a[i])printf("*");
                if(a[i])printf("%d",a[i]);
                j=a[i];
                k=1;
            }
            else k++;
            if(!a[i])break; //改为直到型循环可能更直接
        }
        printf("\n");
        printf("输入需分解的数(任意字符退出):");
    }
    return 0;
}

仔细看了你在13楼的书本提示，发现少使用了一个技巧：就是找最小因子不一定从2开始，这可以极大地降低时间复杂度。
修改后的代码如下（降低复杂度的修改部分有注释）：

#include<stdio.h>
void ff(int n,int a[],int l)
{//分解质因数，质因数都存储在数组a中
    int i,j;
    j=2;
    if(l)j=a[l-1];  //最小因子从上次筛选获得，可减少时间复杂度
    for(i=j;(i*i<=n)&&(n%i);i++);
    if(i==1||i*i>n)a[l]=n;
    else
    {
        a[l]=i;
        ff(n/i,a,++l);
    }
}
int main()
{
    int i,j,k,n,a[100]={0};
    printf("输入需分解的数(任意字符退出):");
    while(scanf("%d",&n))
    {
        for(i=0;i<100;i++)a[i]=0;
        ff(n,a,0);
        printf("%d=",n);
        for(i=0,j=0,k=1;i<100;i++)
        {
            if(a[i]!=j)
            {
                if(j&&k>1)printf("^%d",k);
                if(i&&a[i])printf("*");
                if(a[i])printf("%d",a[i]);
                j=a[i];
                k=1;
            }
            else k++;
            if(!a[i])break; //改为直到型循环可能更直接
        }
        printf("\n");
        printf("输入需分解的数(任意字符退出):");
    }
    return 0;
}

 

谢谢美丽的版主。。。

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <conio.h>

// 項結構
struct Item
{
    unsigned short p;        // 素因子
    size_t k;                // 指數

    Item(unsigned short p, size_t k = 0)
    {
        this->p = p;
        this->k = k;
    }

    bool operator==(const Item& item)
    {
        return (this->p == item.p) && (this->k == item.k);
    }

    bool operator!=(const Item& item)
    {
        return (this->p != item.p) || (this->k != item.k);
    }
};

// 裝入素數表
const std::vector<unsigned short> Load_PrimeList(const char* filename)
{
    std::vector<unsigned short> list;
    FILE* file;
    if (fopen_s(&file, filename, "rb") == 0)
    { 
        unsigned short i;
        while (fread(&i, sizeof(i), 1, file) == 1)
        {
            list.push_back(i);
        }
        fclose(file);
    }

    return list;
}

int main(void)
{
    const std::vector<unsigned short> prime_list(Load_PrimeList("Prime.DAT"));
    if (prime_list.empty())
    {
        return EXIT_FAILURE;
    }

    long int n_array[] = { 1024, 1323, 97532468, 1, 3, 65521 * 65534 };

    for (unsigned long int n : n_array)
    {
        printf_s("%u = ", n);

        std::vector<Item> items;
        std::vector<unsigned short>::const_iterator it = prime_list.cbegin();
        if (n != 1)
        {
            while (n != 1)
            {
                if (n % *it == 0)
                {
                    if (items.empty() || (items.back().p != *it))
                    {
                        items.push_back(Item(*it));
                    }
                    if (items.back().p == *it)
                    {
                        ++items.back().k;
                    }
                    n /= *it;
                }
                else
                {
                    ++it;
                }
            }

            for (Item item : items)
            {
                printf_s("%u", item.p);
                if (item.k > 1)
                {
                    printf_s("^%u", item.k);
                }
                if (item != items.back())
                {
                    printf_s(" * ");
                }
            }
        }
        else
        {
            printf_s("%u", n);
        }
        putchar('\n');
    }

    printf_s("\nPress any key to continue...");
    _getch();
    return EXIT_SUCCESS;
}

[此贴子已经被作者于2015-11-5 22:54编辑过]

提速的關鍵是回避計算素數，事先做好一張素數表，作爲數據庫使用，那是永久性的，在所有需要使用素數的場合均適用，那個功夫値得花。擁有這張表，那麽問題就歸化爲字符串與整數互換那樣簡單的操作，遞歸與非遞歸，在這裏區分，對任何精度的整數而言，效率都不會低，而且非遞歸算法比遞歸效率高、消耗少，事實上邏輯也更清晰。

版主这些C语言库从哪学来的。有专门的书么？

MSDN