codeforces 546D Soldier and Number Game

题意就是求a!/b!的素因子的个数

也就是a!的-b!的

重复的算多次

#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000010;
bool is_prime[maxn];
int p, mpf[maxn], nf[maxn], sum[maxn];

void init(int n) {
 p=nf[1]=sum[1]=0;
 is_prime[0]=is_prime[1]=false;
 for(int i=2; i<n; i++) {
  mpf[i]=i;
  is_prime[i]=true;
 }
 for(int i=2; i<n; i++) {
  for(int j=2*i; j<n; j += i) {
   if(is_prime[i] && mpf[j]>i) mpf[j]=i;
   is_prime[j]=false;
  }
 }
 for(int i=2; i<n; i++) nf[i]=nf[i/mpf[i]]+1;
 for(int i=2; i<n; i++) sum[i]=sum[i-1]+nf[i];

}

int main() {
 int t, a, b;
 init(maxn);
 for(scanf("%d", &t); t--; printf("%d\n", sum[a]-sum[b])) scanf("%d%d", &a, &b);
 return 0;
}

codeforces 546D Soldier and Number Game

原文：http://blog.csdn.net/zhangwenchi/article/details/47296363