lightoj 1035【暴力】

思路：

预处理一下素数数组，然后暴力计算就好了。

类似处理素数因子；

#include <cstdio>

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long LL;

const long long INF=0x3f3f3f3f;

const int N=1e2+10;

int prime[N],ans[N];

bool isPrime[N];

int num;

void init()

{

    num=0;

    memset(isPrime,false,sizeof(isPrime));

    for(int i=2;i<=100;i++)

    {

        if(isPrime[i]) continue;

        prime[++num]=i;

        for(int j=i+i;j<=100;j+=i)

            isPrime[j]=true;

    }

}

int main()

{

    init();

    int n;

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int m=n;

        int temp;

        memset(ans,0,sizeof(ans));

        for(int k=2;k<=n;k++)

        {

            temp=k;

            for(int i=1;i<=num;i++)

            {

                while(temp%prime[i]==0)

                {

                    ans[prime[i]]++;

                    temp/=prime[i];

                }

                if(temp==1)

                    break;

            }

        }

        printf("Case %d: %d = ",cas++,m);

        int flag=0;

        for(int i=1;i<=num;i++)

        {

            if(ans[prime[i]])

            {

                if(flag) printf(" * ");

                printf("%d (%d)",prime[i],ans[prime[i]]);

                flag=1;

            }

        }

        puts("");

    }

    return 0;

}

巴特西

lightoj 1035【暴力】

最新文章

热门文章