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 kotlin.math.sqrt
 
fun main() {
    println("First 199 terms of the möbius function are as follows:")
    print("    ")
    for (n in 1..199) {
        print("%2d  ".format(mobiusFunction(n)))
        if ((n + 1) % 20 == 0) {
            println()
        }
    }
}
 
private const val MU_MAX = 1000000
private var MU: IntArray? = null
 
//  Compute mobius function via sieve
private fun mobiusFunction(n: Int): Int {
    if (MU != null) {
        return MU!![n]
    }
 
    //  Populate array
    MU = IntArray(MU_MAX + 1)
    val sqrt = sqrt(MU_MAX.toDouble()).toInt()
    for (i in 0 until MU_MAX) {
        MU!![i] = 1
    }
    for (i in 2..sqrt) {
        if (MU!![i] == 1) {
            //  for each factor found, swap + and -
            for (j in i..MU_MAX step i) {
                MU!![j] *= -i
            }
            //  square factor = 0
            for (j in i * i..MU_MAX step i * i) {
                MU!![j] = 0
            }
        }
    }
    for (i in 2..MU_MAX) {
        when {
            MU!![i] == i -> {
                MU!![i] = 1
            }
            MU!![i] == -i -> {
                MU!![i] = -1
            }
            MU!![i] < 0 -> {
                MU!![i] = 1
            }
            MU!![i] > 0 -> {
                MU!![i] = -1
            }
        }
    }
    return MU!![n]
}