Homework SourseWrite and test a C implementation of the Mobius function Mn
Write and test a C implementation of the Mobius function M(n) defined as follows
M(n) = 1 if n = 1
= 0 if any prime factor is contained in N more than once
= (1)p if n is the product of p different prime factors
Examples
M(78) = 1 78 = 2 * 3 * 13
M(34) = 1 34 = 2 * 17
M(45) = 0 45 = 3 * 3 * 5
The first values of M(n) are shown in this table n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
M(n) 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0
Extra credit: Using random numbers, estimate the probabilities that M(n) returns 1, 0, +1
Solution
#include <stdio.h>
#include <math.h>
int pFactors(int n)
{
int a=n;
int i=2;
int m=0;
int c=0;
int f=0;
while(a > 1)
{
c = 0;
while(a%i == 0)
{
a=a/i; f = f+1; c =c+1;
}
i = i + 1 ;
if(c > 1)
{
return 0;
}
else
{
;
}
}
return f;
}
void Mfunc(int n)
{
int mob,x;
if(n == 1) // condition 1
mob = 1;
else
{
x = pFactors(n);
if(x != 0) // condition 3
{
mob = pow(-1,x);
printf(\"%i\ \",mob);
}
else // condition 2
{
mob = 0;
printf(\"%i\ \",mob);
}
}
}
int main()
{
int a = 78;
printf(\"Mobius Function value for %i is \",a);
Mfunc(a);
int b = 34;
printf(\"Mobius Function value for %i is \",b);
Mfunc(b);
int c = 45;
printf(\"Mobius Function value for %i is \",c);
Mfunc(c);
return 0;
}
Sample Output:
Mobius Function value for 78 is -1
Mobius Function value for 34 is 1
Mobius Function value for 45 is 0
