-
Notifications
You must be signed in to change notification settings - Fork 5
/
euler.lua
executable file
·207 lines (183 loc) · 4.39 KB
/
euler.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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#!/usr/bin/env lua
-- Euler #1
-- Answer: 233168
--
-- If we list all the natural numbers below 10 that are multiples of 3 or 5,
-- we get 3, 5, 6 and 9. The sum of these multiples is 23.
--
-- Find the sum of all the multiples of 3 or 5 below 1000.
function euler1()
n = 0
for i = 3, 999, 1 do
if (i % 3 == 0) or (i % 5 == 0) then
n = n + i
end
end
return n
end
-- Euler #2
-- Answer: 4613732
--
-- Each new term in the Fibonacci sequence is generated by adding the previous
-- two terms. By starting with 1 and 2, the first 10 terms will be:
--
-- 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
--
-- Find the sum of all the even-valued terms in the sequence which do not
-- exceed four million.
function euler2()
n, a, b = 2, 1, 2
while true do
c = a + b
if c > 4000000 then
break
end
if c % 2 == 0 then
n = n + c
end
a, b = b, c
end
return n
end
-- Euler #3:
-- Answer: 6857
--
-- The prime factors of 13195 are 5, 7, 13 and 29.
--
-- What is the largest prime factor of the number 600851475143 ?
function euler3()
n = 600851475143
for i = math.ceil(math.sqrt(n)), 1, -1 do
if n % i == 0 and is_prime(i) then
return i
end
end
-- How do I raise an exception?
return -1
end
function is_prime(n)
for i = math.ceil(math.sqrt(n)), 2, -1 do
if n % i == 0 then
return false
end
end
return true
end
-- Problem #4
-- Answer: 906609
--
-- A palindromic number reads the same both ways. The largest
-- palindrome made from the product of two 2-digit numbers is 9009 =
-- 91 99.
--
-- Find the largest palindrome made from the product of two 3-digit
-- numbers.
function euler4()
r = 0
for a = 100, 1000, 1 do
for b = 100, 1000, 1 do
c = a * b
s = tostring(c)
if s == string.reverse(s) then
r = math.max(c, r)
end
end
end
return r
end
-- Problem #5
-- Answer: 232792560
--
-- 2520 is the smallest number that can be divided by each of the
-- numbers from 1 to 10 without any remainder.
--
-- What is the smallest number that is evenly divisible by all of the
-- numbers from 1 to 20?
function divisible_by_all(n, ds)
for _, d in ipairs(ds) do
if n % d ~= 0 then
return false
end
end
return true
end
function euler5()
n = 2520
while true do
if divisible_by_all(n, {20, 19, 18, 17, 16, 15, 14, 13, 12, 11}) then
return n
end
n = n + 1
end
end
-- Problem #6
-- Answer: 25164150
--
-- The sum of the squares of the first ten natural numbers is,
-- 1² + 2² + ... + 10² = 385
-- The square of the sum of the first ten natural numbers is,
-- (1 + 2 + ... + 10)² = 55² = 3025
-- Hence the difference between the sum of the squares of the first
-- ten natural numbers and the square of the sum is 3025 - 385 = 2640.
--
-- Find the difference between the sum of the squares of the first one
-- hundred natural numbers and the square of the sum.
function euler6()
sum = 0
sum_sq = 0
for i = 1,100,1 do
sum = sum + i
sum_sq = sum_sq + (i * i)
end
return (sum * sum) - sum_sq
end
-- Problem #7
-- Answer: 104743
--
-- By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
--
-- What is the 10001st prime number?
function euler7()
n = 2
primes = {}
while true do
is_prime = true
for _, v in ipairs(primes) do
if n % v == 0 then
is_prime = false
break
end
end
if is_prime then
if # primes >= 10000 then
return n
end
table.insert(primes, n)
end
n = n + 1
end
end
eulers = {
euler1,
euler2,
euler3,
euler4,
euler5,
euler6,
euler7,
}
function main()
if arg[1] then
for _, a in ipairs(arg) do
print("#" .. a .. ": " .. eulers[tonumber(a)]())
end
else
for index, euler in ipairs(eulers) do
print("#" .. tostring(index) .. ": " .. tostring(euler()))
end
end
end
-------------------------------------------------------
-- "main"... is there more idiomatic stuff missing?
-- (e.g. if __name__ == "__main__" type of stuff?)
main()