[NYOJ 517]最小公倍数

テーマリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=517
考え方：1~nの最小公倍数を求めると、nに等しいx^i以下の積（xは質数で、しかもiはできるだけ大きい、x^i<=n）を求める。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

#define MAXN 1000
#define MAXM 1000

using namespace std;

int primes[MAXN],tot=0;
bool isPrime[MAXM];
int ans[MAXN]; //   

void GetPrime()
{
    memset(isPrime,true,sizeof(isPrime));
    for(int i=2;i<MAXM;i++)
    {
        if(isPrime[i])
        {
            primes[++tot]=i;
            for(int j=i*2;j<MAXM;j+=i)
                isPrime[j]=false;
        }
    }
}

int main()
{
    GetPrime();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int len=1;
        memset(ans,0,sizeof(ans));
        ans[1]=1;
        for(int i=1;primes[i]<=n;i++)
        {
            int x=primes[i];
            while(x<=n) x*=primes[i];
            x/=primes[i];
            for(int i=1;i<=len;i++) ans[i]*=x;
            for(int i=1;i<=len;i++)
            {
                ans[i+1]+=ans[i]/10;
                ans[i]%=10;
            }
            while(ans[len+1]>0)
            {
                len++;
                ans[len+1]+=ans[len]/10;
                ans[len]%=10; 
            }
        }
        for(int i=len;i>=1;i--)
            printf("%d",ans[i]);
        printf("
");
    }
    return 0;
}