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


package main
 
import "fmt"
 
func möbius(to int) []int {
    if to < 1 {
        to = 1
    }
    mobs := make([]int, to+1) // all zero by default
    primes := []int{2}
    for i := 1; i <= to; i++ {
        j := i
        cp := 0      // counts prime factors
        spf := false // true if there is a square prime factor
        for _, p := range primes {
            if p > j {
                break
            }
            if j%p == 0 {
                j /= p
                cp++
            }
            if j%p == 0 {
                spf = true
                break
            }
        }
        if cp == 0 && i > 2 {
            cp = 1
            primes = append(primes, i)
        }
        if !spf {
            if cp%2 == 0 {
                mobs[i] = 1
            } else {
                mobs[i] = -1
            }
        }
    }
    return mobs
}
 
func main() {
    mobs := möbius(199)
    fmt.Println("Möbius sequence - First 199 terms:")
    for i := 0; i < 200; i++ {
        if i == 0 {
            fmt.Print("    ")
            continue
        }
        if i%20 == 0 {
            fmt.Println()
        }
        fmt.Printf("  % d", mobs[i])
    }
}