-
Notifications
You must be signed in to change notification settings - Fork 319
/
ch-1.lua
executable file
·111 lines (104 loc) · 2.58 KB
/
ch-1.lua
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#! /usr/bin/lua
-- by Michael Anderson at
-- https://stackoverflow.com/questions/8722620/comparing-two-index-tables-by-index-value-in-lua
function recursive_compare(t1,t2)
-- Use usual comparison first.
if t1==t2 then return true end
-- We only support non-default behavior for tables
if (type(t1)~="table") then return false end
-- They better have the same metatables
local mt1 = getmetatable(t1)
local mt2 = getmetatable(t2)
if( not recursive_compare(mt1,mt2) ) then return false end
-- Check each key-value pair
-- We have to do this both ways in case we miss some.
-- TODO: Could probably be smarter and not check those we've
-- already checked though!
for k1,v1 in pairs(t1) do
local v2 = t2[k1]
if( not recursive_compare(v1,v2) ) then return false end
end
for k2,v2 in pairs(t2) do
local v1 = t1[k2]
if( not recursive_compare(v1,v2) ) then return false end
end
return true
end
function genprimes(mx)
local primesh = {}
for i = 2, 3 do
primesh[i] = true
end
for i = 6, mx, 6 do
for j = i-1, i+1, 2 do
if j <= mx then
primesh[j]=true
end
end
end
local q={2,3,5,7}
local p=table.remove(q,1)
local mr=math.floor(math.sqrt(mx))
while p <= mr do
if primesh[p] ~= nil then
for i = p*p,mx,p do
primesh[i] = nil
end
end
if #q < 2 then
table.insert(q,q[#q]+4)
table.insert(q,q[#q]+2)
end
p=table.remove(q,1)
end
local primes = {}
for k,v in pairs(primesh) do
table.insert(primes,k)
end
table.sort(primes)
return primes
end
function primepartition(n, divs)
local pl = genprimes(n)
local p = {{}}
while #p > 0 do
local pa = table.remove(p)
if #pa == divs then
local sum = 0
for i,v in ipairs(pa) do
sum = sum + v
end
if sum == n then
return pa
end
else
local px = {}
for i,v in ipairs(pa) do
px[v] = true
end
for i,pq in ipairs(pl) do
if px[pq] == nil then
local pb = {}
for j,pk in ipairs(pa) do
table.insert(pb,pk)
end
table.insert(pb,pq)
table.insert(p,pb)
end
end
end
end
return {n}
end
if recursive_compare(primepartition(18,2), {13, 5}) then
io.write("Pass")
else
io.write("FAIL")
end
io.write(" ")
if recursive_compare(primepartition(19,3), {11, 5, 3}) then
io.write("Pass")
else
io.write("FAIL")
end
print("")