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


import std.math;
import std.stdio;
 
immutable MU_MAX = 1_000_000;
 
int mobiusFunction(int n) {
    static initialized = false;
    static int[MU_MAX + 1] MU;
 
    if (initialized) {
        return MU[n];
    }
 
    // populate array
    MU[] = 1;
    int root = cast(int) sqrt(cast(real) MU_MAX);
 
    for (int i = 2; i <= root; i++) {
        if (MU[i] == 1) {
            // for each factor found, swap + and -
            for (int j = i; j <= MU_MAX; j += i) {
                MU[j] *= -i;
            }
            // square factor = 0
            for (int j = i * i; j <= MU_MAX; j += i * i) {
                MU[j] = 0;
            }
        }
    }
 
    for (int 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;
        }
    }
 
    initialized = true;
    return MU[n];
}
 
void main() {
    writeln("First 199 terms of the möbius function are as follows:");
    write("    ");
    for (int n = 1; n < 200; n++) {
        writef("%2d  ", mobiusFunction(n));
        if ((n + 1) % 20 == 0) {
            writeln;
        }
    }
}