最近学算术基本定理，想用C程序实现它，即输入任意正整数（>1），将该整数分解为素数之积，例如10=2*5，12=2*2*3，18=2*3*3，按类似格式输出结果。。想了很久没能做到完全分解，希望高手能给予指导，一起讨论，不甚感激。。。。

因数分解好像到现在也没有很好的算法，也许我才疏学浅，有知道的还请不吝赐教。
写一段代码抛砖引玉吧。没有使用筛法求素数是不想消耗太多的内存

#include<stdio.h>
#define SIZE    10000
int prime[SIZE];
void init()
{
    int i, a, n;
    prime[0] = 2;
    for(n = 1, a = 3; n < SIZE; a += 2)
    {
        for(i = 0; i < n; i++)
            if(a % prime[i] == 0) break;
        if(i == n) prime[n++] = a;
    }
}
void print(int a)
{
    int i;
    printf("%d = ", a);
    for(i = 0; i < SIZE && a % prime[i]; i++);
    if(i == SIZE)
    {
        printf("over flow.\n");
        return;
    }
    printf("%d", prime[i]);
    for(a /= prime[i]; a > 1 && i < SIZE; i++)
        for(; a % prime[i] == 0; a /= prime[i])
            printf(" * %d", prime[i]);
    printf("\n");
    if(a > 1) printf("over flow.\n");
}
int main()
{
    int a;
    init();
    printf("input number : ");
    scanf("%d", &a);
    print(a);
    return 0;
}

顶2L

#include<stdio.h>
int main()
{
    int n=0,i,t=1,s=1,temp;
    int sushu(int m);
    printf("Input a number(>1):");
    scanf("%d",&n);
    printf("%d=",n);
    temp=n;
    if(sushu(n)==1)
    {
        printf("%d",n);
    }
    else
    {
        do
        {
            for(i=2;i<=temp/2;i++)
            {
                if(sushu(i)==1&&temp%i==0)
                {
                    if(t==1)
                    {
                        printf("%d",i);
                        t=0;
                    }
                    else
                    {
                        printf("*%d",i);
                    }
                    s*=i;
                    temp=temp/i;
                    if(sushu(temp)==1)
                    {
                        printf("*%d",temp);
                        s*=temp;
                    }
                    break;
                }
            }
        }while(n>s);
    }
    printf("\n");
    return 0;
}
int sushu(int m)//验证是否为素数
{
    int i=2,flag=1;
    for(;i<=m/2;i++)//查找到二分之一时就可以结束了
        if(m%i==0)
        {
            flag=0;//不是素数，标示量设置为1
            break;
        }
    return flag;//返回标示量，1表示是素数，0相反
}

请问兄台你学习算法都看些什么书？

手机码字不太方便，写下大致思路：
1.首先用一个变量t存储输入的值
2.接着从i = 2开始进行循环，先用函数isPrime()判断i是否是素数，是则继续下一步，不是则continue，i＋＋；
3.接着判断i能否整除t，能则把i存到一个数组中去，同时t /= i, 然后把i的值重置为2；
4.t > 1时循环以上步骤
。。。。
主要步骤就这些，中学信息竞赛的题里面好像有这道，当时我弟上课的时候我也去了，回去在电脑里面翻一翻没准可以翻出来==

#include<stdio.h>
int main()
{
    int i=2,sum,d;
    scanf("%d",&sum);
    printf("%d=",sum);
    while(i<sum){
        if(sum%i!=0)
            i=i+1;
        if(sum%i==0){
            sum=sum/i;
            if(sum==1)break;
        printf("%d*",i);
        }
        if(sum==i){
            i-=1;
        }
    }
    if(sum==1)
        d=sum*i;
    printf("%d",d);
    return 0;
}我也想了一个,但是有限制,望指教

如果上面的int 改为long long 更好一点

恕我愚钝，你的算法思路我确实没看明白，能否再加点解释。。。。不甚感激。。。

膜拜。。。兄弟平时看些什么书？有关算法的。