/* Problem 2--The Mobius Function
   This was straightforward.  First we compute a list of all valid
   primes.  From there, we compute how many of these primes divide the
   input integers. */

#include <stdio.h>
#include <stdlib.h>

FILE *in, *out;
int Primes[10000], Pct;

int main (int argc, char **argv);
void GetPrimes (void);
int M (int n);

int main (int argc, char **argv) {

  int i;

 in = fopen ("prob2.in","r");
 out = fopen ("prob2.out","w");
 GetPrimes();
 while (1) {
  fscanf (in,"%d",&i);
  if (i==-1) break;
  fprintf (out,"M(%d) = %d\n\n",i,M(i));
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* GetPrimes puts all primes up to 10000 into an array.*/
void GetPrimes (void) {

  int i, p;

 for (i = 2; i <=10000; i++) {
  int IP = 1;        /* check up to the square root */
  for (p = 0; p < Pct && Primes[p]*Primes[p]<=i; p++)
   if (i%Primes[p]==0) {IP = 0; break;}
  if (IP) Primes[Pct++] = i;
 }
}

/* M computes the Mobius function */
int M (int n) {

  int p, result;

 if (n==1) return 1;
 result = -1;    /* divide up to the square root, the initial -1 */
                 /* represents the final prime remaining. */
 for (p = 0; p < Pct && Primes[p]*Primes[p]<=n; p++)
  if (n%Primes[p]==0) {
   n /= Primes[p];
   if (n%Primes[p]==0) return 0;
   result = -result;
  }
 return result;
}