ACM模版

描述

题解

先素数筛一下素数，然后合数分解搞搞事情，典型的模版题，无脑敲代码就行了。

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1e4 + 10;

int prime[MAXN];

void get_prime()
{
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i < MAXN; i++)
    {
        if (!prime[i])
        {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j < prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

long long fac[100][2];
int fatCnt;

// 合数分解
int getFac(long long x)
{
    fatCnt = 0;
    long long tmp = x;
    for (int i = 1; prime[i] * prime[i] <= tmp; i++)
    {
        fac[fatCnt][1] = 0;
        if (tmp % prime[i] == 0)
        {
            fac[fatCnt][0] = prime[i];
            while (tmp % prime[i] == 0)
            {
                fac[fatCnt][1]++;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
    if (tmp != 1)
    {
        fac[fatCnt][0] = tmp;
        fac[fatCnt++][1] = 1;
    }

    return fatCnt;
}

int a, b;

int main()
{
    get_prime();

    while (cin >> a >> b)
    {
        for (int i = a; i <= b; i++)
        {
            cout << i << '=';
            getFac(i);
            for (int j = 0; j < fatCnt; j++)
            {
                for (int k = 0; k < fac[j][1]; k++)
                {
                    cout << fac[j][0];
                    if (j + 1 == fatCnt && k + 1 == fac[fatCnt - 1][1])
                    {
                        cout << '\n';
                    }
                    else
                    {
                        cout << '*';
                    }
                }
            }
        }
    }

    return 0;
}

参考

《合数相关》