Question

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

Answer 1

C code:

#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\n",mob);

}
else // condition 2
{
mob = 0;
       printf("%i\n",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