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


 
program moebius
    use iso_fortran_env, only: output_unit
 
    integer, parameter          :: mu_max=1000000, line_break=20
    integer, parameter          :: sqroot=int(sqrt(real(mu_max)))
    integer                     :: i, j
    integer, dimension(mu_max)  :: mu
 
    mu = 1
 
    do i = 2, sqroot
        if (mu(i) == 1) then
            do j = i, mu_max, i
                mu(j) = mu(j) * (-i)
            end do
 
            do j = i**2, mu_max, i**2
                mu(j) = 0
            end do
        end if
    end do
 
    do i = 2, mu_max
        if (mu(i) == i) then
            mu(i) = 1
        else if (mu(i) == -i) then
            mu(i) = -1
        else if (mu(i) < 0) then
            mu(i) = 1
        else if (mu(i) > 0) then
            mu(i) = -1
        end if
    end do
 
    write(output_unit,*) "The first 199 terms of the Möbius sequence are:"
    write(output_unit,'(3x)', advance="no") ! Alignment of first number
    do i = 1, 199
        write(output_unit,'(I2,x)', advance="no") mu(i)
        if (modulo(i+1, line_break) == 0) write(output_unit,*)
    end do
end program moebius
 