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


function buildArray(size, value)
    local tbl = {}
    for i=1, size do
        table.insert(tbl, value)
    end
    return tbl
end
 
MU_MAX = 1000000
sqroot = math.sqrt(MU_MAX)
mu = buildArray(MU_MAX, 1)
 
for i=2, sqroot do
    if mu[i] == 1 then
        -- for each factor found, swap + and -
        for j=i, MU_MAX, i do
            mu[j] = mu[j] * -i
        end
        -- square factor = 0
        for j=i*i, MU_MAX, i*i do
            mu[j] = 0
        end
    end
end
 
for i=2, MU_MAX do
    if mu[i] == i then
        mu[i] = 1
    elseif mu[i] == -i then
        mu[i] = -1
    elseif mu[i] < 0 then
        mu[i] = 1
    elseif mu[i] > 0 then
        mu[i] = -1
    end
end
 
print("First 199 terms of the mobius function are as follows:")
io.write("    ")
for i=1, 199 do
    io.write(string.format("%2d  ", mu[i]))
    if (i + 1) % 20 == 0 then
        print()
    end
end