因数：也称约数，如果整数a除以整数b，商为整数且余数为0，则称b 是a的因数。例如：1、2、3、6 都是6的因数。 素数：也称质数，是指在大于1的自然数中，除了1和它本身以外没有其他因数的数。例如：2、3、5 是素数，4、6、8 不是素数。 平方数：指的是可以写成某个整数的平方的数。例如：4(2^2)、9(3^2)、16(4^2)都是平方数。 莫比乌斯函数 μ(n) 是指以下的函数： 1) 若n=1，则μ(n)=1 2) 若n的因数中有大于1的平方数，则μ(n)=0 3) 若n的因数中没有大于1的平方数，且n=P1，P2……Pk，则μ(n)=(-1)k，注：P,P…P.表示k(k≤1)个不同素数的乘积 例如： 1) 8的因数有1、2、4、8，其中大于1的平方数有4，所以μ(8)=0； 2) 15的因数有1、3、5、15，没有大于1的平方数，且15=3×5，所以μ(15)=(-1)2=1； 3) 30的因数有1、2、3、5、6、10、15、30，没有大于1的平方数，且30=2×3×5，所以μ(30)=(-1)3=-1 给定两个正整数m、n，请计算m到n之间(含m和n)所有整数的莫比乌斯函数值之和。 输入格式 一行输入两个正整数m和n(1≤m≤n≤2×107) ，整数之间以一个空格隔开 输出格式 输出一个整数，表示m到n之间(含m和n)所有整数的莫比乌斯函数值之和 输入样例 1 10 输出样例 -1
正确答案：参考程序（Python）：m,n=map(int,input().split());mu=[1]*(n+1);p=[];isC=[0]*(n+1);for i in range(2,n+1):if not isC[i]:p.append(i);mu[i]=-1;for j in p:if i*j>n:break;isC[i*j]=1;if i%j==0:mu[i*j]=0;break;else:mu[i*j]=-mu[i];print(sum(mu[m:n+1]))。样例1 10→-1。核心：线性筛莫比乌
试卷来源：202409(第15届)蓝桥杯C++编程青少组(国赛_中高级)真题