54 lines
1.0 KiB
Nim
54 lines
1.0 KiB
Nim
import std/[math, sequtils, strformat]
|
|
|
|
func getStep(n: int): int {.inline.} =
|
|
result = 1 + n shl 2 - n shr 1 shl 1
|
|
|
|
func primeFac(n: int): seq[int] =
|
|
var
|
|
maxq = int(sqrt(float(n)))
|
|
d = 1
|
|
q: int = 2 + (n and 1) # Start with 2 or 3 according to oddity.
|
|
|
|
while q <= maxq and n %% q != 0:
|
|
q = getStep(d)
|
|
inc d
|
|
if q <= maxq:
|
|
let q1 = primeFac(n /% q)
|
|
let q2 = primeFac(q)
|
|
result = concat(q2, q1, result)
|
|
else:
|
|
result.add(n)
|
|
|
|
func squareFree(num: int): bool =
|
|
let fact = primeFac num
|
|
|
|
for i in fact:
|
|
if fact.count(i) > 1:
|
|
return false
|
|
|
|
return true
|
|
|
|
func mobius(num: int): int =
|
|
if num == 1: return num
|
|
|
|
let fact = primeFac num
|
|
|
|
for i in fact:
|
|
## check if it has a squared prime factor
|
|
if fact.count(i) == 2:
|
|
return 0
|
|
|
|
if num.squareFree:
|
|
if fact.len mod 2 == 0:
|
|
return 1
|
|
else:
|
|
return -1
|
|
|
|
when isMainModule:
|
|
echo "The first 199 möbius numbers are:"
|
|
|
|
for i in 1..199:
|
|
stdout.write fmt"{mobius(i):4}"
|
|
if i mod 20 == 0:
|
|
echo "" # print newline
|