Skip to content

Instantly share code, notes, and snippets.

@lucasgruwez

lucasgruwez/01.py

Last active September 2, 2017 10:34
Show Gist options

  • Select an option

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

Select an option

Learn more about clone URLs
Save lucasgruwez/eed2754de2994a3e95c9b1303225a9d3 to your computer and use it in GitHub Desktop.
Download ZIP
Project Euler solutions (1-20)
Raw
01.py
import time
def get_divisors(n):
res = []
for i in range(1, n):
if i % 3 == 0 or i % 5 == 0:
res.append(i)
return res
start = time.time()
answer = sum(get_divisors(100))
end = time.time()
total = end - start
print('Problem 1: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 1: 2318
# Done in 2.6941299438476562e-05 seconds.
Raw
02.py
import time
def get_even_fib_numbers(n):
# n is the number that the fibonaci numbers cant exceed
fib_list = []
a = 1
b = 2
while b < n:
if b % 2 == 0:
fib_list.append(b)
c = a + b
a = b
b = c
return fib_list
start = time.time()
answer = sum(get_even_fib_numbers(4000000))
end = time.time()
total = end - start
print('Problem 2: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 2: 4613732
# Done in 2.47955322265625e-05 seconds.
Raw
03.py
import time
t0 = time.time()
def prime_factors(n):
factors = []
i = 2
while i*i < n:
while n % i == 0:
factors.append(i)
n /= i
i += 1
if n != 1:
factors.append(int(n))
return factors
start = time.time()
answer = max(prime_factors(600851475143))
end = time.time()
total = end - start
print('Problem 3: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 3: 6857
# Done in 0.0005464553833007812 seconds.
Raw
04.py
import time
def is_palindrome(n):
str_n = str(n)
return bool(str_n == str_n[::-1])
def list_pal():
pals = []
for i in range(100, 1000):
for j in range(100, 1000):
if is_palindrome(i * j):
pals.append(i*j)
return pals
start = time.time()
answer = max(list_pal())
end = time.time()
total = end - start
print('Problem 4: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 4: 906609
# Done in 0.5668458938598633 seconds.
Raw
05.py
import functools
import time
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
start = time.time()
answer = functools.reduce(lcm, range(1, 21))
end = time.time()
total = end - start
print('Problem 5: ' + str(answer) + '\nDone in ' + str(total) + 'seconds.')
# Problem 5: 232792560
# Done in 2.1457672119140625e-05seconds.
Raw
06.py
import time
def sum_of_squares(n):
squares = []
for i in range(1, n+1):
squares.append(i*i)
return sum(squares)
def square_of_sum(n):
sum_ = (n+1)*n / 2
return int(sum_*sum_)
start = time.time()
answer = square_of_sum(100) - sum_of_squares(100)
end = time.time()
total = end - start
print('Problem 6: ' + str(answer) + '\nDone in ' + str(total) + 'seconds.')
# Problem 6: 25164150
# Done in 3.886222839355469e-05seconds.
Raw
07.py
import time
def check_prime(n):
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 get_primes(n):
primes = []
i = 2
while len(primes) < n:
if check_prime(i):
primes.append(i)
if i != 2:
i += 2
if i == 2:
i += 1
return primes
start = time.time()
answer = get_primes(10001)
answer = answer[len(answer) - 1]
end = time.time()
total = end - start
print('Problem 7: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 7: 104743
# Done in 0.26560187339782715 seconds.
Raw
08.py
import time
number = ''
number += '73167176531330624919225119674426574742355349194934'
number += '96983520312774506326239578318016984801869478851843'
number += '85861560789112949495459501737958331952853208805511'
number += '12540698747158523863050715693290963295227443043557'
number += '66896648950445244523161731856403098711121722383113'
number += '62229893423380308135336276614282806444486645238749'
number += '30358907296290491560440772390713810515859307960866'
number += '70172427121883998797908792274921901699720888093776'
number += '65727333001053367881220235421809751254540594752243'
number += '52584907711670556013604839586446706324415722155397'
number += '53697817977846174064955149290862569321978468622482'
number += '83972241375657056057490261407972968652414535100474'
number += '82166370484403199890008895243450658541227588666881'
number += '16427171479924442928230863465674813919123162824586'
number += '17866458359124566529476545682848912883142607690042'
number += '24219022671055626321111109370544217506941658960408'
number += '07198403850962455444362981230987879927244284909188'
number += '84580156166097919133875499200524063689912560717606'
number += '05886116467109405077541002256983155200055935729725'
number += '71636269561882670428252483600823257530420752963450'
def get_largest_product(n):
n = list(n)
products = []
for i in range(len(n) - 13):
p1, p2, p3, p4 = int(n[i]), int(n[i+1]), int(n[i+2]), int(n[i+3])
p5, p6, p7, p8 = int(n[i+4]), int(n[i+5]), int(n[i+6]), int(n[i+7])
p9, p10, p11, p12 = int(n[i+8]), int(n[i+9]), int(n[i+10]), int(n[i+11])
p13 = int(n[i+12])
p = p1*p2*p3*p4*p5*p6*p7*p8*p9*p10*p11*p12*p13
products.append(p)
return max(products)
start = time.time()
answer = get_largest_product(number)
end = time.time()
total = end - start
print('Problem 8: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 8: 23514624000
# Done in 0.004210710525512695 seconds.
Raw
09.py
import time
def pythag_triplet(n):
triplets = []
a = 1
b = 1
c = 1
done = False
while done == False:
if a*a + b*b == c*c:
triplets.append([a, b, c, a+b+c])
if a+b+c == 1000:
return a*b*c
if c > n:
c = 1
if a > n:
a = 1
if b > n:
done = True
return triplets
b += 1
a += 1
else:
c += 1
start = time.time()
answer = pythag_triplet(500)
end = time.time()
total = end - start
print('Problem 9: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 9: 31875000
# Done in 11.817609548568726 seconds.
Raw
10.py
import time
def check_prime(n):
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 get_primes(n):
primes = []
i = 2
while i < n:
if check_prime(i):
primes.append(i)
if i != 2:
i += 2
if i == 2:
i += 1
return primes
start = time.time()
answer = sum(get_primes(2000000))
end = time.time()
total = end - start
print('Problem 10: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 10: 142913828922
# Done in 17.783731698989868 seconds.
Raw
11.py
import time
grid = []
grid.append('08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08')
grid.append('49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00')
grid.append('81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65')
grid.append('52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91')
grid.append('22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80')
grid.append('24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50')
grid.append('32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70')
grid.append('67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21')
grid.append('24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72')
grid.append('21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95')
grid.append('78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92')
grid.append('16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57')
grid.append('86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58')
grid.append('19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40')
grid.append('04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66')
grid.append('88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69')
grid.append('04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36')
grid.append('20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16')
grid.append('20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54')
grid.append('01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48')
j = 0
for i in grid:
grid[j] = i.split(' ')
j2 = 0
for k in grid[j]:
grid[j][j2] = int(k)
j2 += 1
j += 1
def get_four_consec_max():
four_consec = []
for r in range(20):
row = grid[r]
for i in range(16):
four_consec.append(row[i] * row[i+1] * row[i+2] * row[i+3])
for c in range(20):
for i in range(16):
four_consec.append(grid[i][c] * grid[i+1][c] * grid[i+2][c] * grid[i+3][c])
for r in range(16):
for c in range(16):
four_consec.append(grid[r][c] * grid[r+1][c+1] * grid[r+2][c+2] * grid[r+3][c+3])
for r in range(16):
for c in range(-19, -2):
r, c = -r, -c
four_consec.append(grid[r][c] * grid[r+1][c-1] * grid[r+2][c-2] * grid[r+3][c-3])
maximum = max(four_consec)
return maximum
start = time.time()
answer = get_four_consec_max()
end = time.time()
total = end - start
print('Problem 11: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 11: 70600674
# Done in 0.0013654232025146484 seconds.
Raw
12.py
import time
def get_tri_num(n):
return n * (n+1) / 2
def get_divisors(n):
divisors = []
for i in range(1, int(n**.5) + 1):
if n % i == 0:
divisors.append(i)
if n // i != i:
divisors.append(n // 1)
return divisors
def get_answer(n):
most_divs = 0
i = 1
while most_divs < n:
tri = get_tri_num(i)
divs = get_divisors(tri)
if most_divs < len(divs):
most_divs = len(divs)
i += 1
return int(tri)
start = time.time()
answer = get_answer(500)
end = time.time()
total = end - start
print('Problem 12: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 12: 76576500
# Done in 8.450052261352539 seconds.
Raw
13.py
import time
hundred_nums = []
hundred_nums.append(37107287533902102798797998220837590246510135740250)
hundred_nums.append(46376937677490009712648124896970078050417018260538)
hundred_nums.append(74324986199524741059474233309513058123726617309629)
hundred_nums.append(91942213363574161572522430563301811072406154908250)
hundred_nums.append(23067588207539346171171980310421047513778063246676)
hundred_nums.append(89261670696623633820136378418383684178734361726757)
hundred_nums.append(28112879812849979408065481931592621691275889832738)
hundred_nums.append(44274228917432520321923589422876796487670272189318)
hundred_nums.append(47451445736001306439091167216856844588711603153276)
hundred_nums.append(70386486105843025439939619828917593665686757934951)
hundred_nums.append(62176457141856560629502157223196586755079324193331)
hundred_nums.append(64906352462741904929101432445813822663347944758178)
hundred_nums.append(92575867718337217661963751590579239728245598838407)
hundred_nums.append(58203565325359399008402633568948830189458628227828)
hundred_nums.append(80181199384826282014278194139940567587151170094390)
hundred_nums.append(35398664372827112653829987240784473053190104293586)
hundred_nums.append(86515506006295864861532075273371959191420517255829)
hundred_nums.append(71693888707715466499115593487603532921714970056938)
hundred_nums.append(54370070576826684624621495650076471787294438377604)
hundred_nums.append(53282654108756828443191190634694037855217779295145)
hundred_nums.append(36123272525000296071075082563815656710885258350721)
hundred_nums.append(45876576172410976447339110607218265236877223636045)
hundred_nums.append(17423706905851860660448207621209813287860733969412)
hundred_nums.append(81142660418086830619328460811191061556940512689692)
hundred_nums.append(51934325451728388641918047049293215058642563049483)
hundred_nums.append(62467221648435076201727918039944693004732956340691)
hundred_nums.append(15732444386908125794514089057706229429197107928209)
hundred_nums.append(55037687525678773091862540744969844508330393682126)
hundred_nums.append(18336384825330154686196124348767681297534375946515)
hundred_nums.append(80386287592878490201521685554828717201219257766954)
hundred_nums.append(78182833757993103614740356856449095527097864797581)
hundred_nums.append(16726320100436897842553539920931837441497806860984)
hundred_nums.append(48403098129077791799088218795327364475675590848030)
hundred_nums.append(87086987551392711854517078544161852424320693150332)
hundred_nums.append(59959406895756536782107074926966537676326235447210)
hundred_nums.append(69793950679652694742597709739166693763042633987085)
hundred_nums.append(41052684708299085211399427365734116182760315001271)
hundred_nums.append(65378607361501080857009149939512557028198746004375)
hundred_nums.append(35829035317434717326932123578154982629742552737307)
hundred_nums.append(94953759765105305946966067683156574377167401875275)
hundred_nums.append(88902802571733229619176668713819931811048770190271)
hundred_nums.append(25267680276078003013678680992525463401061632866526)
hundred_nums.append(36270218540497705585629946580636237993140746255962)
hundred_nums.append(24074486908231174977792365466257246923322810917141)
hundred_nums.append(91430288197103288597806669760892938638285025333403)
hundred_nums.append(34413065578016127815921815005561868836468420090470)
hundred_nums.append(23053081172816430487623791969842487255036638784583)
hundred_nums.append(11487696932154902810424020138335124462181441773470)
hundred_nums.append(63783299490636259666498587618221225225512486764533)
hundred_nums.append(67720186971698544312419572409913959008952310058822)
hundred_nums.append(95548255300263520781532296796249481641953868218774)
hundred_nums.append(76085327132285723110424803456124867697064507995236)
hundred_nums.append(37774242535411291684276865538926205024910326572967)
hundred_nums.append(23701913275725675285653248258265463092207058596522)
hundred_nums.append(29798860272258331913126375147341994889534765745501)
hundred_nums.append(18495701454879288984856827726077713721403798879715)
hundred_nums.append(38298203783031473527721580348144513491373226651381)
hundred_nums.append(34829543829199918180278916522431027392251122869539)
hundred_nums.append(40957953066405232632538044100059654939159879593635)
hundred_nums.append(29746152185502371307642255121183693803580388584903)
hundred_nums.append(41698116222072977186158236678424689157993532961922)
hundred_nums.append(62467957194401269043877107275048102390895523597457)
hundred_nums.append(23189706772547915061505504953922979530901129967519)
hundred_nums.append(86188088225875314529584099251203829009407770775672)
hundred_nums.append(11306739708304724483816533873502340845647058077308)
hundred_nums.append(82959174767140363198008187129011875491310547126581)
hundred_nums.append(97623331044818386269515456334926366572897563400500)
hundred_nums.append(42846280183517070527831839425882145521227251250327)
hundred_nums.append(55121603546981200581762165212827652751691296897789)
hundred_nums.append(32238195734329339946437501907836945765883352399886)
hundred_nums.append(75506164965184775180738168837861091527357929701337)
hundred_nums.append(62177842752192623401942399639168044983993173312731)
hundred_nums.append(32924185707147349566916674687634660915035914677504)
hundred_nums.append(99518671430235219628894890102423325116913619626622)
hundred_nums.append(73267460800591547471830798392868535206946944540724)
hundred_nums.append(76841822524674417161514036427982273348055556214818)
hundred_nums.append(97142617910342598647204516893989422179826088076852)
hundred_nums.append(87783646182799346313767754307809363333018982642090)
hundred_nums.append(10848802521674670883215120185883543223812876952786)
hundred_nums.append(71329612474782464538636993009049310363619763878039)
hundred_nums.append(62184073572399794223406235393808339651327408011116)
hundred_nums.append(66627891981488087797941876876144230030984490851411)
hundred_nums.append(60661826293682836764744779239180335110989069790714)
hundred_nums.append(85786944089552990653640447425576083659976645795096)
hundred_nums.append(66024396409905389607120198219976047599490197230297)
hundred_nums.append(64913982680032973156037120041377903785566085089252)
hundred_nums.append(16730939319872750275468906903707539413042652315011)
hundred_nums.append(94809377245048795150954100921645863754710598436791)
hundred_nums.append(78639167021187492431995700641917969777599028300699)
hundred_nums.append(15368713711936614952811305876380278410754449733078)
hundred_nums.append(40789923115535562561142322423255033685442488917353)
hundred_nums.append(44889911501440648020369068063960672322193204149535)
hundred_nums.append(41503128880339536053299340368006977710650566631954)
hundred_nums.append(81234880673210146739058568557934581403627822703280)
hundred_nums.append(82616570773948327592232845941706525094512325230608)
hundred_nums.append(22918802058777319719839450180888072429661980811197)
hundred_nums.append(77158542502016545090413245809786882778948721859617)
hundred_nums.append(72107838435069186155435662884062257473692284509516)
hundred_nums.append(20849603980134001723930671666823555245252804609722)
hundred_nums.append(53503534226472524250874054075591789781264330331690)
def first_ten(number):
ln = list(str(number))
ans = ''
for i in range(10):
ans += ln[i]
return int(ans)
start = time.time()
answer = first_ten(sum(hundred_nums))
end = time.time()
total = end - start
print('Problem 13: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 13: 5537376230
# Done in 3.457069396972656e-05 seconds.
Raw
14.py
import time
def collatz(n):
nums = []
while n != 1:
nums.append(n)
if n % 2 == 0:
n = int(n/2)
else:
n = 3*n + 1
nums.append(1)
return nums
def get_longest(n):
longestSeq = 1
num = 1
for i in range(1, n):
am = len(collatz(i))
if am > longestSeq:
longestSeq = am
num = i
return num
start = time.time()
answer = get_longest(1000000)
end = time.time()
total = end - start
print('Problem 14: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 14: 837799
# Done in 50.31860303878784 seconds.
Raw
15.py
import time
# Using the central binominal coeficient
def factorial(n):
res = 1
for i in range(1, n+1):
res *= i
return res
def for_grid(sz):
return int(factorial(2 * sz) / factorial(sz)**2)
start = time.time()
answer = for_grid(20)
end = time.time()
total = end - start
print('Problem 15: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 15: 137846528820
# Done in 2.7179718017578125e-05 seconds.
Raw
16.py
import time
def sum_digits(n):
ln = list(str(n))
ans = 0
for i in ln:
ans += int(i)
return ans
start = time.time()
answer = sum_digits(2**1000)
end = time.time()
total = end - start
print('Problem 16: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 16: 1366
# Done in 0.00011610984802246094 seconds.
Raw
17.py
from num2words import num2words
import time
string = ''
for i in range(1, 1001):
word = num2words(i)
for char in word:
if char != '-' and char != ' ':
string += char
start = time.time()
answer = len(string)
end = time.time()
total = end - start
print('Problem 17: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 17: 21124
# Done in 3.0994415283203125e-06 seconds.
Raw
18.py
import time
tri_num=[]
tri_num.append('75'.split(' '))
tri_num.append('95 64'.split(' '))
tri_num.append('17 47 82'.split(' '))
tri_num.append('18 35 87 10'.split(' '))
tri_num.append('20 04 82 47 65'.split(' '))
tri_num.append('19 01 23 75 03 34'.split(' '))
tri_num.append('88 02 77 73 07 63 67'.split(' '))
tri_num.append('99 65 04 28 06 16 70 92'.split(' '))
tri_num.append('41 41 26 56 83 40 80 70 33'.split(' '))
tri_num.append('41 48 72 33 47 32 37 16 94 29'.split(' '))
tri_num.append('53 71 44 65 25 43 91 52 97 51 14'.split(' '))
tri_num.append('70 11 33 28 77 73 17 78 39 68 17 57'.split(' '))
tri_num.append('91 71 52 38 17 14 91 43 58 50 27 29 48'.split(' '))
tri_num.append('63 66 04 68 89 53 67 30 73 16 69 87 40 31'.split(' '))
tri_num.append('04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'.split(' '))
x, y = 0, 0
for i in tri_num:
y = 0
for j in i:
tri_num[x][y] = int(j)
y += 1
x+= 1
for i in range(len(tri_num)-1,-1,-1):
for j in range(0,i):
maximum = max(tri_num[i][j],tri_num[i][j+1])
tri_num[i-1][j] += maximum
start = time.time()
answer = tri_num[0][0]
end = time.time()
total = end - start
print('Problem 18: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 18: 1074
# Done in 1.9073486328125e-06 seconds.
Raw
19.py
from datetime import date
import time
sundays = 0
for year in range(1901, 2001):
for month in range(1, 13):
if date(year, month, 1).weekday() == 6:
sundays += 1
start = time.time()
answer = sundays
end = time.time()
total = end - start
print('Problem 19: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 19: 171
# Done in 7.152557373046875e-07 seconds.
Raw
20.py
import time
def factorial(n):
res = 1
for i in range(1, n+1):
res *= i
return res
def sum_digits(n):
ln = list(str(n))
res = 0
for i in ln:
res += int(i)
return res
start = time.time()
answer = sum_digits(factorial(100))
end = time.time()
total = end - start
print('Problem 20: ' + str(answer) + '\nDone in ' + str(total) + ' seconds.')
# Problem 20: 648
# Done in 8.487701416015625e-05 seconds.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment