primes.lua

View source code here on GitHub!

primes(stop)
Returns:

An iterator over the prime numbers, optionally up to stop

Return type:

table

prime_factors(n)
Returns:

An iterator over the prime factors of n

Return type:

table

 1local function primes(stop)
 2    local prime = 1
 3    local candidate = 2
 4    local sieve = {}
 5
 6    local function next_prime(cand)
 7        local steps = sieve[cand]
 8
 9        if steps then
10            for _, step in ipairs(steps) do
11                local value = cand + step
12                sieve[value] = sieve[value] or {}
13                table.insert(sieve[value], step)
14            end
15            sieve[cand] = nil
16            return next_prime(cand + 1)
17        else
18            sieve[cand * cand] = { cand }
19            return cand
20        end
21    end
22
23    local function next()
24        if stop and prime >= stop then
25            sieve = {}
26            return nil, "Tried to exceed given limit"
27        end
28
29        prime = next_prime(candidate)
30        candidate = prime + 1
31
32        if stop and prime >= stop then
33            sieve = {}
34            return nil, "Tried to exceed given limit"
35        end
36
37        return prime
38    end
39
40    return {
41        next = next
42    }
43end
44
45local function prime_factors(n)
46    local pgen = primes()
47    local p = pgen.next()
48
49    local function next()
50        if n == 1 then
51            return nil
52        end
53
54        while p and n % p ~= 0 do
55            p = pgen.next()
56        end
57
58        if p == nil then
59            return nil
60        end
61
62        if n < 0 then
63            n = -n
64            return -1
65        end
66
67        n = math.floor(n / p)
68        return p
69    end
70
71    return {
72        next = next,
73    }
74end
75
76return {
77    primes = primes,
78    prime_factors = prime_factors,
79}