The classical Möbius function: μ(n) is an important multiplicative function in number theory and combinatorics.

There are several ways to implement a Möbius function.

A fairly straightforward method is to find the prime factors of a positive integer n, then define μ(n) based on the sum of the primitive factors. It has the values {−1, 0, 1} depending on the factorization of n:

 μ(1) is defined to be 1.
 μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
 μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
 μ(n) = 0 if n has a squared prime factor.


Task

 Write a routine (function, procedure, whatever) μ(n) to find the Möbius number for a positive integer n.
 Use that routine to find and display here, on this page, at least the first 99 terms in a grid layout. (Not just one long line or column of numbers.)


See also

 Wikipedia: Möbius function


Related Tasks

 Mertens function


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main() {
    const int MU_MAX = 1000000;
    int i, j;
    int *mu;
    int sqroot;
 
    sqroot = (int)sqrt(MU_MAX);
 
    mu = malloc((MU_MAX + 1) * sizeof(int));
 
    for (i = 0; i < MU_MAX;i++) {
        mu[i] = 1;
    }
 
    for (i = 2; i <= sqroot; i++) {
        if (mu[i] == 1) {
            // for each factor found, swap + and -
            for (j = i; j <= MU_MAX; j += i) {
                mu[j] *= -i;
            }
            // square factor = 0
            for (j = i * i; j <= MU_MAX; j += i * i) {
                mu[j] = 0;
            }
        }
    }
 
    for (i = 2; i <= MU_MAX; i++) {
        if (mu[i] == i) {
            mu[i] = 1;
        } else if (mu[i] == -i) {
            mu[i] = -1;
        } else if (mu[i] < 0) {
            mu[i] = 1;
        } else if (mu[i] > 0) {
            mu[i] = -1;
        }
    }
 
    printf("First 199 terms of the möbius function are as follows:\n    ");
    for (i = 1; i < 200; i++) {
        printf("%2d  ", mu[i]);
        if ((i + 1) % 20 == 0) {
            printf("\n");
        }
    }
 
    free(mu);
    return 0;
}