本文共 1219 字，大约阅读时间需要 4 分钟。

1441 士兵的数字游戏

题目

两个士兵正在玩一个游戏，游戏开始的时候，第一个士兵为第二个士兵选一个正整数n。然后第二个士兵要玩尽可能多的轮数。每一轮要选择一个正整数x>1，且n要是x的倍数，然后用n/x去代替n。当n变成1的时候，游戏就结束了，第二个士兵所得的分数就是他玩游戏的轮数。

为了使游戏更加有趣，第一个士兵用 a! / b! 来表示n。k!表示把所有1到k的数字乘起来。

那么第二个士兵所能得到的最大分数是多少呢？

输入

单组测试数据。

输出

对于每一组数据，输出第二个士兵能拿到的最多分数。

输入样例

2

输出样例

2

#include 
   
    #include 
    
     #include 
     
      using namespace std;typedef long long ll;const int maxn = 5e6 + 5;int vis[maxn];ll sum[maxn];void init_prim() {
       vis[0] = vis[1] = 1;    sum[0] = sum[1] = 0;    for (int i = 2; i < maxn; i++) {
           if (!vis[i]) {
               sum[i] = 1;            for (int j = i + i; j < maxn; j += i) {
                   vis[j] = 1;                int n = j, num = 0;                while (n % i == 0) {
                       num++;                    n /= i;                }                sum[j] += num;            }        }    }    for (int i = 1; i < maxn; i++) {
           sum[i] += sum[i - 1];    }}int main() {
       init_prim();    int t;    scanf("%d", &t);    while (t--) {
           int a, b;        scanf("%d%d", &a, &b);        printf("%lld\n", sum[a] - sum[b]);    }    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108429123 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！