简单来讲,isp数组是记录第i个数是不是质数的数组。
f函数是返回j里面包含多少个i相乘的函数。
第一层循环的i是质因子,第二层循环的j是通过i生成出来的,如果j在(l,r)的区间内,最终答案加f(j,i)(因为题目说重复的质因子要加多次)。
代码中包含了质数筛选的思路,改造后才变成了现在的代码。
本代码不像其它代码先枚举(l,r)中的数,再枚举它的质因子,而是正好相反,所以时间很短。
代码:
#include<iostream>
using namespace std;
int l, r, ans;
bool isp[2000001];
int f(int j, int i){
int sum = 0;
while(j%i == 0) sum++, j /= i;
return sum;
}
int main(){
cin >> l >> r;
for(int i = 2;i <= r;i++){
if(isp[i] == 1) continue;
for(int j = i;j <= r;j += i){
isp[j] = 1;
if(j >= l) ans += f(j, i);
}
}
printf("%d", ans);
return 0;
}