因数:也称约数,如果整数a除以整数b,商为整数且余数为0,则称b 是a的因数。
例如:1、2、3、6 都是 6的因数。素数:也称质数,是指在大于1的自然数中,除了1和它本身以外没有其他因数的数。例如:2、3、5 是素数,4、6、8 不是素数平方数:指的是可以写成某个整数的平方的数。例如:4(22)、9(32)、16(42)都是平方数。
莫比乌斯函数 μ(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)个不同素数的乘积。
例如:
8 的因数有 1、2、4、8,其中大于1的平方数有 4,所以 μ(8)=0;
15 的因数有 1、3、5、15,没有大于1的平方数,且15=3*5,所以μ(15)=(-1)2= 1;
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(),整数之间以一个空格隔开
输出格式
输出一个整数,表示 m 到 n之间(含 m 和 n)所有整数的莫比乌斯函数值之和
输入样例
1 10
输出
-1