Project Euler Problem 1-5

https://projecteuler.net/problem=1

import time

sum = 0

time_start = time.time()

for i in range(1, 1000):
    if i%3 == 0 or i%5 == 0:
        sum += i

time_end = time.time()

print(sum)
print(time_end-time_start)

# sum : 233168

※

 

https://projecteuler.net/problem=2

import time

time_start = time.time()
sum = 0
fib_1 = 1
fib_2 = 1

while fib_2<4000000:
    fib_tmp = fib_2
    fib_2 = fib_1 + fib_tmp
    fib_1 = fib_tmp

    if fib_2 % 2== 0:
        sum+=fib_2
    
time_end = time.time()

print(sum)
print(time_end-time_start)

# sum : 4613732

https://projecteuler.net/problem=3

import time
import math

time_start = time.time()

def prime_check(n):

    if n==2:
        return True

    for i in range(2, math.floor(math.sqrt(n))+1):
        if n%i==0:
            return False
        
    return True

def max_p_factor(n):
    tmp = n
    prime_factor_list = []
    while tmp!=1:
        for i in range(2, tmp):
            if prime_check(i):
                if tmp%i==0:
                    prime_factor_list.append(i)
                    while tmp%i==0:
                        tmp /= i
            if tmp == 1:
                break
    return prime_factor_list[len(prime_factor_list)-1]

time_end = time.time()

print(max_p_factor(600851475143))
print(time_end-time_start)

# 6857

 

https://projecteuler.net/problem=4

import time
import math

time_start = time.time()
l = []

for i in range(100, 1000):
    for j in range(100, i+1):
        if str(i*j) == str(i*j)[::-1]:
            l.append(i*j)

l.sort(reverse = True)
time_end = time.time()

print(l[0])
print(time_end-time_start)

# 906609

 

https://projecteuler.net/problem=5

gcd함수를 정의 후 lcm(a, b)*gcd(a, b) = a*b 활용

 

import time

goal = 1

time_start = time.time()

def gcd(a, b):
    if a%b == 0:
        return b
    return gcd(b, a%b)

for i in range(1, 20):
    goal = goal*(i+1)/gcd(goal, i+1)	# lcm(a, b) * gcd(a, b) = a*b 이용

time_end = time.time()

print(goal)
print(time_end-time_start)

# goal : 232792560