Skip to content

Instantly share code, notes, and snippets.

@lucasgruwez

lucasgruwez/21.py

Last active September 30, 2017 12:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lucasgruwez/1d936f0136bfce051d587019fdc7123a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lucasgruwez/1d936f0136bfce051d587019fdc7123a to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler solutions (21- 40)
Raw
21.py
import time
def get_divisors(n):
res = [1]
i = 2
while i*i < n:
if n % i == 0:
res.append(i)
res.append(n // i)
i += 1
if i*i == n:
res.append(i)
return res
def is_amicable(n):
if sum(get_divisors(sum(get_divisors(n)))) == n:
if sum(get_divisors(n)) == n:
return False
return sum(get_divisors(n))
return False
start = time.time()
ams = []
for i in range(1, 10001):
if is_amicable(i):
ams.append(i)
answer = sum(ams)
end = time.time()
total = end - start
print('Problem 21: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 21: 31626
# Done in 0.18555212020874023 seconds.
Raw
22.py
import time
start = time.time()
names = open('p022_names.txt')
names_str = names.read()
names_list = names_str.split('","')
names_list[0] = 'MARY'
names_list[len(names_list) - 1] = 'ALONSO'
names_list = sorted(names_list)
values = {'A':1,'B':2,'C':3,'D':4,'E':5,'F':6,'G':7,'H':8,'I':9,'J':10,'K':11,'L':12,'M':13,'N':14,'O':15,'P':16,'Q':17,'R':18,'S':19,'T':20,'U':21,'V':22,'W':23,'X':24,'Y':25,'Z':26}
def score(string):
scr = 0
for char in string:
scr += values[char]
return scr
scores = []
for i in range(len(names_list)):
scores.append(score(names_list[i]) * (i+1))
answer = sum(scores)
end = time.time()
total = end - start
print('Problem 22: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 22: 871198282
# Done in 0.00740361213684082 seconds.
Raw
23.py
import time
def get_divisors(n):
res = [1]
i = 2
while i*i < n:
if n % i == 0:
res.append(i)
res.append(n // i)
i += 1
if i*i == n:
res.append(i)
return res
def is_abundant(n):
return sum(get_divisors(n)) > n
start = time.time()
abundants = []
for i in range(1, 28124):
if is_abundant(i):
abundants.append(i)
ints = [x for x in range(28123)]
for i in range(len(abundants)):
for j in range(i,28123):
if abundants[i]+abundants[j] < 28123:
ints[abundants[i]+abundants[j]] = 0
else:
break
answer = sum(ints)
end = time.time()
total = end - start
print('Problem 23: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 23: 4179871
# Done in 5.247133731842041 seconds.
Raw
24.py
from itertools import permutations
import time
start = time.time()
p = permutations(range(10))
perms = []
for i in p:
string = ''
for j in i:
string += str(j)
perms.append(string)
answer = perms[999999]
end = time.time()
total = end - start
print('Problem 24: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 24: 2783915460
# Done in 27.06125497817993 seconds.
Raw
25.py
import time
start = time.time()
fib = [1, 1]
while len(str(fib[len(fib) - 1])) < 1000:
l = len(fib)
fib.append(fib[l-2] + fib[l-1])
answer = len(fib)
end = time.time()
total = end - start
print('Problem 25: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 25: 4782
# Done in 0.03628945350646973 seconds.
Raw
26.py
import time
start = time.time()
def get_cycle(d):
for i in range(1, d+1):
if 10**i % d == 1:
return i
return 0
cycles = [get_cycle(i) for i in range(1, 1001)]
answer = cycles.index(max(cycles)) + 1
end = time.time()
total = end - start
print('Problem 26: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 26: 983
# Done in 0.6796298027038574 seconds.
Raw
27.py
import time
def prime(n):
if n < 0:
return False
i = 2
while i*i <= n:
if n % i == 0:
return False
if i != 2:
i += 2
if i == 2:
i += 1
return True
def quad(a, b, n):
return n**2 + a*n + b
def check_quad(a, b):
i = 0
while prime(quad(a,b,i)):
i += 1
return i
start = time.time()
maxi = 0
A, B = 0, 0
for i in range(-1000, 1000):
for j in range(-1001, 1001):
n = check_quad(i,j)
if n > maxi:
maxi = n
A, B = i, j
answer = A*B
end = time.time()
total = end - start
print('Problem 27: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 27: -59231
# Done in 4.78370475769043 seconds.
Raw
28.py
import time
start = time.time()
def diagonal_1(x):
return 4*x**2+4*x+1
def diagonal_2(x):
return 4*x**2-2*x+1
def diagonal_3(x):
return 4*x**2+1
def diagonal_4(x):
return 4*x**2+2*x+1
def square(x):
n = int((x-1) / 2)
nums = []
for i in range(1, n+1):
nums.append(diagonal_1(i))
nums.append(diagonal_2(i))
nums.append(diagonal_3(i))
nums.append(diagonal_4(i))
return sum(nums) + 1
answer = square(1001)
end = time.time()
total = end - start
print('Problem 28: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 28: 669171001
# Done in 0.0021097660064697266 seconds.
Raw
29.py
import time
start = time.time()
res = []
for i in range(2, 101):
for j in range(2, 101):
if not i**j in res:
res.append(i**j)
answer = len(res)
end = time.time()
total = end - start
print('Problem 29: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 29: 9183
# Done in 1.2614822387695312 seconds.
Raw
30.py
import time
start = time.time()
def check(n):
list_n = [int(i)**5 for i in list(str(n))]
return sum(list_n) == n
answer = 0
for i in range(2, 200000):
if check(i):
answer += i
end = time.time()
total = end - start
print('Problem 30: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 30: 443839
# Done in 0.9066269397735596 seconds.
Raw
31.py
import time
start = time.time()
coins = [1,2,5,10,20,50,100,200]
answers = [0]*201
answers[0] = 1
for x in coins:
for i in range(x, 201):
answers[i] += answers[i-x]
answer = answers[200]
end = time.time()
total = end - start
print('Problem 31: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 31: 73682
# Done in 0.0006198883056640625 seconds.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment