-
-
Notifications
You must be signed in to change notification settings - Fork 2.6k
/
mobius.go
40 lines (37 loc) · 1.08 KB
/
mobius.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// mobius.go
// description: Returns μ(n)
// details:
// For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity.
// It has values in {−1, 0, 1} depending on the factorization of n into prime factors:
// μ(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.
// wikipedia: https://en.wikipedia.org/wiki/M%C3%B6bius_function
// time complexity: O(n)
// space complexity: O(1)
// author: Akshay Dubey (https://github.com/itsAkshayDubey)
// see mobius_test.go
package math
import (
"github.com/TheAlgorithms/Go/math/prime"
)
// Mu is the Mobius function
// This function returns μ(n) for given number
func Mu(n int) int {
if n <= 1 {
return 1
}
var primeFactorCount int
for i := 1; i <= n; i++ {
if n%i == 0 && prime.OptimizedTrialDivision(int64(i)) {
if n%(i*i) == 0 {
return 0
}
primeFactorCount += 1
}
}
if primeFactorCount%2 == 0 {
return 1
}
return -1
}