题目链接：https://ac.nowcoder.com/acm/problem/211962

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109631931

题目

我们定义 除 之外的所有因子
即 除 外所有因子的
询问从

输入

输入两个正整数

输出

输出一个正整数表示答案

样例输入

5 7

样例输出

13

数据范围

对于 的数据，
对于 的数据，
对于 的数据，

思路

这道题是一道数学题。

题目的 函数要的是一个数所有除了 的因子的 。

我们大概想想就会发现，如果这一个数分解质因数可以分解出不止一种质数，那的出来的 函数值就是 。
（因为这个数至少会有这两个质数为因子，而两个质数的 又是一，那的出来就只能是 了）

那我们就先素数筛选法找出 以内的质数，然后对于每一个质数，就枚举多少个这个质数乘在一起，对于每一个数，它对答案的贡献就是那个质数。
最后还没有对答案产生贡献的数，就是由不止一个质数乘起来得到的数，对答案的贡献就是 。

（ 的话就是对答案贡献 ，所以可以算在由不止一个质数乘起来得到的数里面）

代码

#include<cstdio>

using namespace std;

long long a, b, ans, susu[10000024], tot;
bool yes[10000024];

int main() {
    scanf("%lld%lld",&a,&b);   

    for(long long i = 2; i <= b; i++) {
        if(!yes[i]) susu[tot++] = i;
        for(long long j = 0; j < tot && i * susu[j] <= b; j++)
            yes[i * susu[j]] = 1;
    }

    ans = b - a + 1;//先假设全部贡献都是 1

    for(long long i = 0; i < tot; i++)
        for(long long j = susu[i]; j <= b; j *= susu[i])
            if(a <= j) ans += susu[i] - 1;//是质数的贡献，就让贡献加上质数减去之前加上的 1

    printf("%lld", ans);

    return 0;
}