Soldier and Number Game（前缀和，求素数因子）

本文主要是介绍Soldier and Number Game（前缀和，求素数因子），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原文:Soldier and Number Game
大意： 一个士兵给出一个整数，然后另一个士兵找到这个数的因子，这个数变成它本身除去这个因子，这就算是一轮。要求尽可能多的找，当这个数为1时结束。
思路：
对于a!/b!这种，就等同于从b+1累乘至a。

也就是求a, a - 1, a - 2…b +1这些整数能被拆分成多少个素数相乘，把每个的拆分结果相加起来。
考虑前缀和。

#include<stdio.h>
#include<string.h>
#define N 5000000
int f[5000010];
void is_only()
{int i,j,k;memset(f,0,sizeof(f));for(i=2;i<=N;i++){if(f[i]==0){for(j=i;j<=N;j+=i){k=j;while(k%i==0){f[j]++;k/=i;}}}}for(i=2;i<=N;i++)f[i]+=f[i-1];  //前缀和
}
int main()
{int t,i,j,a,b;is_only();scanf("%d",&t);while(t--){scanf("%d%d",&a,&b);int ans=f[a]-f[b];printf("%d\n",ans);}return 0;
}

这篇关于Soldier and Number Game（前缀和，求素数因子）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---