codeforces-546D-Soldier and Number Game【思维】（求质因子个数）

题目链接：点击打开链接

D. Soldier and Number Game time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output

Two soldiers are playing a game. At the beginning first of them chooses a positive integer n and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer x > 1, such that n is divisible by x and replacing n with n / x. When n becomes equal to 1 and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.

To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k.

What is the maximum possible score of the second soldier?

Input

First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.

Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.

Output

For each game output a maximum score that the second soldier can get.

Examples input 2 3 1 6 3 output 2 5

题意：给你 a，b 表示 a！/ b！ 表示的数，你每次可以对这个数除以 x （x >1,且x为这个数的因子（也就尽量从小的开始除）） 使他变成 （a！/  b！）/ x，问你最多可以操作多少次使这个数变成1；

思路：一化简其实就是a*(a-1)*(a-2)…(a-b+1),要次数最多，那每次除的数尽量小，由算数基本定理可知：每个数都可以分解成质数的乘积，质数只有一个质因子，那么我们可以把每个数都分解质因子，质因子不可再分那么质因子的个数就是答案； 数据量较大，应该打表，10^7 N*log(n）内层循环应该对数 9973是一个素数所以找到3000以内的素数就差不多了

代码1：

#include<cstdio> #include<cstring> #define MAX 5000050 using namespace std; bool sushu[MAX]; int dp[MAX]; void init() { memset(dp,0,sizeof(dp)); memset(sushu,true,sizeof(sushu)); sushu[1]=false; for(int i=2;i<MAX;i++) { if(sushu[i]) { for(int j=i;j<MAX;j+=i) { int temp=j; while(temp%i==0) { temp/=i; dp[j]++; } sushu[j]=false; } } } for(int i=1;i<MAX;i++) { dp[i]+=dp[i-1]; } } int main() { int t; scanf("%d",&t); init(); while(t--) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",dp[a]-dp[b]); } return 0; }

代码2： #include<cstdio> #include<cstring> #define M 5000000 using namespace std; int dp[M]; int main() { memset(dp,0,sizeof(dp)); for(int i=2;i<=M;i++) { if(dp[i]==0) { for(int j=i;j<=M;j+=i) { dp[j]=dp[j/i]+1; } } } for(int i=1;i<=M;i++) dp[i]+=dp[i-1]; int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",dp[a]-dp[b]); } return 0; }