UVA 583 素数打表（线性）

题意：将一个给定的数分解为素数乘积的形式输出；

思路：先预处理出素数，再分解，格式模拟上需要花点时间调；

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int num[5000100],v[5000100];
int su[5000100],shu=0;
/*void prepare()
{
    int i,j;
    memset(v,0,sizeof(v));
    for(i=2;i<5000100;i++)
    {
        if(!v[i]) su[shu++]=i;
        if(!v[i])
        for(j=2*i;j<5000100;j+=i)
        {
            v[i]=1;
        }
    }
}*/
void prepare()
{
    int i,j;
    for(i=2;i<5000100;i++)
    {
        if(!v[i]) su[shu++]=i;
        for(j=0;j<shu;j++)
        {
            if(i*su[j]>5000100) break;
            v[i*su[j]]=1;
            if(i%su[j]==0) break;
        }
    }
}
int main()
{
    prepare();
    int i,j,k,flag;
    long long n;
    while(scanf("%lld",&n)!=EOF)
    {
        flag=0;
        if(n==0) break;
        if(n<0) printf("%lld = -1",n),flag=1,n=-n;
        else printf("%lld =",n);
        for(i=0;i<shu;i++)
        {
            if(n==1) break;
            while(n%su[i]==0)
            {
                if(flag==0)
                {
                    flag=1;printf(" %d",su[i]);
                    n/=su[i];
                }
                else
                {
                    n/=su[i];
                    printf(" x %d",su[i]);
                }
            }
        }
        if(n!=1)
        {
            if(flag==1) printf(" x %lld
",n);
            else printf(" %lld
",n);
        }
        else
           printf("
");
    }
    return 0;
}