用C++编写Mobius函数Mobius函数定义为,输入一个正整数N,当N=1时,函数值为1,当N不为1时,首先在稿纸上将它分解质因数,若某质因数的个数大于1,则函数值为0,如N=45,45=3*3*5,3出现了两次,故函数值为0.

Question

用C++编写Mobius函数
Mobius函数定义为,输入一个正整数N,当N=1时,函数值为1,当N不为1时,首先在稿纸上将它分解质因数,若某质因数的个数大于1,则函数值为0,如N=45,45=3*3*5,3出现了两次,故函数值为0.若质因数全都不相同,设有p个,则函数值为（-1）的p次方,如78,78=2*3*13,质因数全都不相同,有3个,所以函数值为（-1）的3次方,为-1.

Answer 1

#include
// 一个数字可以有的最多不同质因数个数
#define MAX_PRIM_FACTOR_AMOUNT 1000
/*
Mobius 函数定义为：
输入一个正整数N,当N=1时,函数值为1,

当N不为1时,首先在稿纸上将它分解质因数.
若某质因数的个数大于1,则函数值为0,
如N=45,45=3*3*5,3出现了两次,故函数值为0.

若质因数全都不相同,设有p个,则函数值为（-1）的p次方,
如78,78=2*3*13,质因数全都不相同,有3个,所以函数值为（-1）的3次方,为-1.
*/
/*
功能：求 Mobius 函数的值
参数：
n 一个正整数
doPrint 是否输出正整数 n 的质因数分解形式.1：输出；0：不输出.

返回：
Mobius 函数的值
*/
int Mobius(unsigned int n, unsigned int doPrint)
{
// 用 m 来临时保存 m 的值.因此 n 的值在运算过程中会被改变.
int m = n;
// 用 i 来枚举 n 的质因数
int i;
// 数字 n 的不同质因数个数
int primeFactorAmount = 0;
// n 的某个质因数 i,出现在 n 中的次数
int countCurrentPrimeFactor = 0;
// Mobius 函数的值.初始值为 -3,表示还没有计算出函数值.
int result = -3;

// 记录所有质因数出现的次数.用于输出质因数分解形式.
int primFactors[MAX_PRIM_FACTOR_AMOUNT][2];

if(n == 0)
{// 【1】n==0 的情况,实际是非法的输入.这里返回 -2.
result = -2;
}
else if(n == 1)
{// 【2】n==1 的情况
result = 1;
}
else
{
for(i=2; i= 1)
{// 数字 i 是数字 n 的质因数
primFactors[primeFactorAmount][0] = i;
primFactors[primeFactorAmount][1] = countCurrentPrimeFactor;
primeFactorAmount ++;

if(countCurrentPrimeFactor > 1)
{// 【3】 n 的某质因数的个数大于 1 的情况
result = 0;
}
}
}

if(result == -3)
{// 【4】 n 有 p 个不同的质因数,返回 (-1)^p
result = (primeFactorAmount%2 ? -1 : 1);
}
}

if(doPrint)
{// 需要输出 n 的质因数分解形式
if(m