Codeforces Round #304 (Div. 2) D Soldier and Number Game
dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。
エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもできる)を覚えておくと、素因数分解が簡単にできることを教えてもらった。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) int sieve[6000000]={}; int dp[6000000]={}; int main(){ sieve[0]=sieve[1]=1; for(int i=2;i*i<=5000000;i++){ for(int j=2;i*j<=5000000;j++){ if(sieve[i*j]) continue; sieve[i*j]=i; } } dp[0]=dp[1]=0; for(int i=2;i<=5000000;i++){ if(sieve[i]==0) dp[i]=1; else dp[i] = dp[i/sieve[i]] + 1; } REP(i,5000000) dp[i+1]+=dp[i]; int t; cin >> t; REP(i,t){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",dp[a]-dp[b]); } return 0; }
cin,cout は遅すぎ