583 - Prime Factors

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<conio.h>
#define M 50000

bool prime[M];
long prm[M];
long factor[M];
int genprime();

int main()
{
    register long i,n,m,s,k;
    //freopen("in.txt","r",stdin);
    genprime();
    while(scanf("%ld",&n)&&n)
    {
        if(n==1||n==-1)
        {
            printf("%d = %ld\n",n,n);
            continue;
        }

        i=k=0,m=n,s=sqrt(n);
        if(n<0)
        {
            factor[k++]=-1;
            n=-1*n;
        }

        for(i=0;prm[i]<=sqrt(n);i++)
        {
            while(n%prm[i]==0)
            {
                factor[k++]=prm[i];
                n=n/prm[i];
            }
        }

        if(n!=1)factor[k++]=n;

        printf("%ld = %ld",m,factor[0]);
        for(i=1;i<k;i++)
            printf(" x %d",factor[i]);
        printf("\n");
    }
    getch();
    exit(0);
}
int genprime()
{
    register unsigned long i,j,s=sqrt(M);
    for(i=1;i<M;i++)
        prime[i]=true;
    for(i=2;i<s;)
    {
        if(prime[i])
            for(j=i+i;j<M;j+=i)
                prime[j]=false;
        for(i++;!prime[i];i++);
    }
    j=0;
    for(i=2;i<M;i++)
        if(prime[i])prm[j++]=i;
    return 0;
}