63 lines
2 KiB
Fennel
63 lines
2 KiB
Fennel
(do ;;; Legendre prime counting function - translation of EasyLang
|
|
|
|
; generate and return a table containing the primes up to sieve-size
|
|
(fn prime-sieve [sieve-size]
|
|
(var sieve {})
|
|
(tset sieve 1 false)
|
|
(for [s-pos 2 sieve-size] (tset sieve s-pos true))
|
|
(for [s-pos 2 (math.floor (math.sqrt sieve-size))]
|
|
(when (. sieve s-pos)
|
|
(for [p (* s-pos s-pos) sieve-size s-pos] (tset sieve p false))
|
|
)
|
|
)
|
|
sieve
|
|
)
|
|
|
|
; construct a sieve of primes up to the maximum we will need
|
|
(var ps-root-1e9 (prime-sieve (math.sqrt 1e9)))
|
|
|
|
; returns a table of primes extracted from a prime sieve
|
|
(fn primes-up-to [n sieve]
|
|
(local result {})
|
|
(for [s-pos 1 n]
|
|
(when (. sieve s-pos) (table.insert result s-pos))
|
|
)
|
|
result
|
|
)
|
|
|
|
(fn legendre-pi [n]
|
|
(if (< n 2) 0
|
|
(= n 2) 1
|
|
;else
|
|
(do (local root-n (math.floor (math.sqrt n)))
|
|
(local primes (primes-up-to root-n ps-root-1e9))
|
|
(local prime-count (length primes))
|
|
|
|
(fn phi [x a-in]
|
|
(var (a sum found-1) (values a-in 0 false))
|
|
(while (and (> a 1) (not found-1))
|
|
(local pa (. primes a))
|
|
(if (<= x pa)
|
|
(set found-1 true)
|
|
;else
|
|
(do (set a (- a 1))
|
|
(set sum (+ sum (phi (// x pa) a)))
|
|
)
|
|
)
|
|
)
|
|
(if found-1
|
|
1
|
|
;else
|
|
(- x (// x 2 ) sum)
|
|
)
|
|
)
|
|
|
|
(- (+ (phi n prime-count) prime-count) 1)
|
|
)
|
|
)
|
|
)
|
|
|
|
(for [i 0 9]
|
|
(print (string.format "10^%d %d" i (legendre-pi (^ 10 i))))
|
|
)
|
|
)
|