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


BEGIN
    # show the first 199 values of the moebius function                 #
    INT sq root = 1 000;
    INT mu max  = sq root * sq root;
    [ 1 : mu max ]INT mu;
    FOR i FROM LWB mu TO UPB mu DO mu[ i ] := 1 OD;
    FOR i FROM 2 TO sq root DO
        IF mu[ i ] = 1 THEN
            # for each factor found, swap + and -                       #
            FOR j FROM i     BY i     TO UPB mu DO mu[ j ] *:= -i OD;
            FOR j FROM i * i BY i * i TO UPB mu DO mu[ j ]  :=  0 OD
        FI
    OD;
    FOR i FROM 2 TO UPB mu DO
        IF   mu[ i ] =  i THEN mu[ i ] :=  1
        ELIF mu[ i ] = -i THEN mu[ i ] := -1
        ELIF mu[ i ] <  0 THEN mu[ i ] :=  1
        ELIF mu[ i ] >  0 THEN mu[ i ] := -1
      # ELSE mu[ i ] =  0 so no change #
        FI
    OD;
    print( ( "First 199 terms of the möbius function are as follows:", newline, "    " ) );
    FOR i TO 199 DO
        print( ( whole( mu[ i ], -4 ) ) );
        IF ( i + 1 ) MOD 20 = 0 THEN print( ( newline ) ) FI
    OD
END