T246836 [LSOT-1] 暴龙的土豆

 [LSOT-1] 暴龙的土豆

题目背景

暴龙爱吃土豆。

 题目描述

给定一个正整数 n。

每次操作可以选两个素数 y,z，其中要求 z 是奇素数。

令 x=y^z，如果 x 能除尽 n 则计为一次有效操作，n 变为 n/x。

现在需要你回答，对于 n 最多能够进行多少次有效操作。

 输入格式

本题有多组数据。

第一行一个正整数 T。

接下来 T行，每行一个正整数 n。

输出格式

对于每组数据，输出答案。

 样例 1

 样例输入 1
2
16
9

 样例输出 1
1
0

 样例 2

 样例输入 2
2
1327104
3623878656000

样例输出 2
5
12

提示

【样例解释】

对于样例一：16 可以变成 2^3 * 2，可以进行一次操作。但是 9 只能变成 3^2，所以不能进行操作。

【数据范围】

「本题采用捆绑测试」

Subtask 1(10 pts)：1 <=n<=10^2，1 <=T<10^2
Subtask 2(20 pts)：1 <= n<=10^6，1 <=T<=10^2；
Subtask 3(30 pts)：1 <= n<=10^12，1 <=T<=10^2；
Subtask 4(40 pts)：无特殊限制。

对于 100%的数据，满足 1<=n<=10^18，1<=T<=10^2。

普及-的水平，埃筛法直接先把1-10^6所有素数弄出来，然后把每个素数*3的数存放到数组里就完事了。

#include <iostream>
using namespace std;
bool isprime[1000001];
long long isprime_3[1000001];
const long long m1 = 1000000;
long long length1 = 0;
void init()
{
    for (long long i = 2; i <= m1; i++)                              /*埃筛法求得1-10^6里面所有素数*/
    {
        if (isprime[i] == 0)
        {
            for (long long j = i * 2; j <= m1; j = j * 2)
            {
                isprime[j] = 1;
            }
        }
    } 
    for (int i = 2; i <= m1; i++)                                   /*把x=y*y*y*，那么我们把每个x遍历出来*/
    {
        if (isprime[i] == 0)
        {
            isprime_3[length1++] = i * i * i;
        }
    }
}
int main()
{
    init();
    int t;
    cin >> t;
    while (t--)
    {
        long long n = 0, temp = 0, sum = 0;
        cin >> n;
        temp = n;
        for (int i = 0; i < length1; i++)
        {
            if (temp >= isprime_3[i])                             /*temp>=isprime_3[i]才能继续做*/
            {
                while (temp % isprime_3[i] == 0)
                {
                    temp = temp / isprime_3[i];
                    sum++;
                }
            }
            else                                                /*比它小结束循环*/
            {
                break;
            }
        }
        cout << sum << endl;
    }
    return 0;
}