오일러 프로젝트의 첫 열 개 문제를 파이썬3로 풀이한 모음이다. 부록으로 오일러프로젝트 문제 풀이에 흔히 사용할 수 있는 “빠르게 동작하는” 함수 몇 가지를 미리 작성하여 덧붙였다.
"""10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다. | |
1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?""" | |
def e001(): | |
print(sum((x for x in range(1, 1000) if x % 3 == 0 or x % 5 ==0))) | |
%time e001() | |
#233168 | |
#Wall time: 1 ms |
"""피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. | |
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … | |
짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?""" | |
def e002(): | |
a, b = 1, 1 | |
s = 0 | |
while b <= 4000000: | |
if b % 2 == 0: | |
s += b | |
a, b = b, (a+b) | |
print(s) | |
%time e002() | |
# 4613732 | |
# Wall time: 0 ns |
"""어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. | |
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. | |
600851475143의 소인수 중에서 가장 큰 수를 구하세요.""" | |
def is_prime(n): | |
if n < 2: | |
return False | |
if n is 2 or n is 3: | |
return True | |
if n % 2 == 0 or n % 3 == 0: | |
return False | |
if n < 9: | |
return True | |
k = 5 | |
l = n ** 0.5 | |
while k <= l: | |
if n % k == 0 or n % (k+2) == 0: | |
return False | |
k += 6 | |
return True | |
def e003(): | |
L = 600851475143 | |
a = 2 | |
while True: | |
if L % a == 0: | |
L = L // a | |
if is_prime(L): | |
print(L) | |
return | |
else: | |
a += 1 | |
# 6857 | |
# Wall time: 0 ns |
"""앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. | |
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다. | |
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?""" | |
def isPalindrome(n): | |
s = str(n) | |
return s == s[::–1] | |
def e004(): | |
print(max([x*y for x in range(100,1000) for y in range(100,1000) if isPalindrome(x*y)])) | |
%time e004() |
"""1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. | |
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?""" | |
from functools import reduce | |
def gcd(a, b): | |
a, b = (a, b) if a > b else (b, a) | |
if b is 0: | |
return b | |
if a % b == 0: | |
return b | |
return gcd(b, (a%b)) | |
def lcm(a, b): | |
g = gcd(a, b) | |
return a * b // g | |
def e005(): | |
result = reduce(lcm, range(1, 21)) | |
print(result) | |
%time e005() |
"""1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합). | |
12 + 22 + … + 102 = 385 | |
1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱). | |
(1 + 2 + … + 10)2 = 552 = 3025 | |
따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 – 385 = 2640 이 됩니다. | |
그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?""" | |
def e006(): | |
s1 = sum((x*x for x in range(1, 101))) | |
s2 = sum(range(1, 101)) ** 2 | |
print(s2 – s1) | |
%time e006() |
"""소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, … 과 같이 됩니다. | |
이 때 10,001번째의 소수를 구하세요.""" | |
def is_prime(n): | |
if n < 2: | |
return False | |
if n is 2 or n is 3: | |
return True | |
if n % 2 == 0 or n % 3 == 0: | |
return False | |
if n < 9: | |
return True | |
k = 5 | |
l = n ** 0.5 | |
while k <= l: | |
if n % k == 0 or n % (k+2) == 0: | |
return False | |
k += 6 | |
return True | |
def e007(): | |
n = 0 | |
i = 2 | |
while n < 10001: | |
if is_prime(i): | |
n += 1 | |
i += 1 | |
print(i–1) | |
%time e007() |
"""다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음). | |
73167176531330624919225119674426574742355349194934 | |
96983520312774506326239578318016984801869478851843 | |
85861560789112949495459501737958331952853208805511 | |
12540698747158523863050715693290963295227443043557 | |
66896648950445244523161731856403098711121722383113 | |
62229893423380308135336276614282806444486645238749 | |
30358907296290491560440772390713810515859307960866 | |
70172427121883998797908792274921901699720888093776 | |
65727333001053367881220235421809751254540594752243 | |
52584907711670556013604839586446706324415722155397 | |
53697817977846174064955149290862569321978468622482 | |
83972241375657056057490261407972968652414535100474 | |
82166370484403199890008895243450658541227588666881 | |
16427171479924442928230863465674813919123162824586 | |
17866458359124566529476545682848912883142607690042 | |
24219022671055626321111109370544217506941658960408 | |
07198403850962455444362981230987879927244284909188 | |
84580156166097919133875499200524063689912560717606 | |
05886116467109405077541002256983155200055935729725 | |
71636269561882670428252483600823257530420752963450 | |
여기서 붉게 표시된 71112의 경우 7, 1, 1, 1, 2 각 숫자를 모두 곱하면 14가 됩니다. | |
이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 5자리 숫자들의 곱을 구할 수 있습니다. | |
이렇게 구할 수 있는 5자리 숫자의 곱 중에서 가장 큰 값은 얼마입니까?""" | |
from functools import reduce | |
s = """73167176531330624919225119674426574742355349194934 | |
96983520312774506326239578318016984801869478851843 | |
85861560789112949495459501737958331952853208805511 | |
12540698747158523863050715693290963295227443043557 | |
66896648950445244523161731856403098711121722383113 | |
62229893423380308135336276614282806444486645238749 | |
30358907296290491560440772390713810515859307960866 | |
70172427121883998797908792274921901699720888093776 | |
65727333001053367881220235421809751254540594752243 | |
52584907711670556013604839586446706324415722155397 | |
53697817977846174064955149290862569321978468622482 | |
83972241375657056057490261407972968652414535100474 | |
82166370484403199890008895243450658541227588666881 | |
16427171479924442928230863465674813919123162824586 | |
17866458359124566529476545682848912883142607690042 | |
24219022671055626321111109370544217506941658960408 | |
07198403850962455444362981230987879927244284909188 | |
84580156166097919133875499200524063689912560717606 | |
05886116467109405077541002256983155200055935729725 | |
71636269561882670428252483600823257530420752963450""".replace("\n", "") | |
def process(s): | |
return reduce(lambda x, y: x * y, [int(x) for x in s]) | |
def e008(): | |
l = len(s) – 5 | |
result = max([process(s[i:i+5]) for i in range(0, l)]) | |
print(result) | |
%time e008() |
"""세 자연수 a, b, c 가 피타고라스 정리 a2 + b2 = c2 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a < b < c ). | |
예를 들면 32 + 42 = 9 + 16 = 25 = 52이므로 3, 4, 5는 피타고라스 수입니다. | |
a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까?""" | |
def e008(): | |
target = 1000 | |
for a in range(1, target//3): | |
for b in range(a+1, (target–a)//2): | |
c = target – a – b | |
if c * c == a*a + b*b: | |
print(a*b*c) | |
return | |
%time e008() | |
# 31875000 | |
# Wall time: 32 ms | |
def e008_2(): | |
(a, b, c) = [(a, b, 1000–a–b) for a in range(1, 333) for b in range(a+1, (1000–a)//2) if (1000–a–b)**2 == a*a + b*b][0] | |
print(a*b*c) |
""" | |
10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. | |
이백만(2,000,000) 이하 소수의 합은 얼마입니까?""" | |
def is_prime(n): | |
if n < 2: | |
return False | |
if n is 2 or n is 3: | |
return True | |
if n % 2 == 0 or n % 3 == 0: | |
return False | |
if n < 9: | |
return True | |
k = 5 | |
l = n ** 0.5 | |
while k <= l: | |
if n % k == 0 or n % (k+2) == 0: | |
return False | |
k += 6 | |
return True | |
def e010(): | |
print(sum((x for x in range(2, 2000001) if is_prime(x)))) | |
%time e010() | |
# 142913828922 | |
# Wall time: 18.2 s |
#-*-coding:utf-8 | |
import itertools | |
from functools import reduce | |
#—— chech if the given number is prime ——– | |
def is_prime(num: int) -> bool: | |
""" | |
Check the given number is prime | |
""" | |
if num == 2: | |
return True | |
if num < 2 or num % 2 == 0: | |
return False | |
if num < 9: | |
return True | |
if num % 3 == 0: | |
return True | |
l = int(num**0.5) | |
f = 5 | |
while f <= l: | |
if num % f == 0 or num % (f+2) == 0: | |
return False | |
f += 6 | |
return True | |
def factor(num): | |
""" | |
break the number down to prime divisors and their frequency. | |
>>> factor(786456) | |
[(2,3), (3,3), (11,1), (331,1)] | |
:type num: int | |
:rtype: [tuple] | |
""" | |
if num in [–1, 0, 1]: | |
return [] | |
if num < 0: | |
num = –num | |
F = [] | |
while num != 1: | |
p = trial_division(num) | |
e = 1 | |
num /= p | |
while num%p == 0: | |
e += 1 | |
num /= p | |
F.append((p, e)) | |
F.sort() | |
return F | |
def trial_division(num, bound=None): | |
""" | |
Return the smallest prime number that could | |
divide the given number. | |
:type num: int | |
:type bound: int | |
:rtype: int | |
""" | |
if num == 1: | |
return 1 | |
for p in [2, 3, 5]: | |
if num%p == 0: | |
return p | |
if bound == None: | |
bound = num | |
dif = [6, 4, 2, 4, 2, 4, 6, 2] | |
m = 7 | |
i = 1 | |
while m <= bound and m*m <= num: | |
if num % m == 0: | |
return m | |
m += dif[i%8] # 7 > 11, 13, 17, 19, 23, 29, 31, 37… | |
i += 1 | |
return num | |
def prime_sieve(bound): | |
""" | |
Return a list of prime numbers from 2 to n. | |
Very fast, (n < 10,000,000) in 0.4 sec. | |
—- | |
Algorithm & Python source: Robert William Hanks | |
http://stackoverflow.com/questions/17773352/python-sieve-prime-numbers | |
""" | |
sieve = [True] * (bound//2) | |
for i in range(3, int(bound**.5)+1, 2): | |
if sieve[i//2]: | |
sieve[i * i // 2::i] = [False] * ((bound – i * i – 1) // (2 * i) + 1) | |
return [2] + [2*i+1 for i in range(1, bound // 2) if sieve[i]] | |
def sumOfDivisors(num): | |
""" | |
Return sum of all proper divisors for given number | |
:type num: int | |
:rtype: int | |
""" | |
sum_ = 1 | |
UPPER_LIMIT = num**0.5 | |
for i in range(2, int(UPPER_LIMIT)+1): | |
if num % i == 0: | |
sum_ += i + num / i | |
if UPPER_LIMIT == int(UPPER_LIMIT): | |
sum_ -= int(UPPER_LIMIT) | |
# if num is perfect square number, | |
# exclude one square root out of sum_ | |
return sum_ | |
FACT = (1, 1, 2, 6, 24, 120, 720, 5040, 40320, 36288) | |
def factorial(num): | |
""" | |
Fast factorial function. | |
:type num: int | |
:rtype: int | |
""" | |
return reduce(lambda x, y: x * y, range(1, num+1), 1) | |
def perms(n, ls): | |
if n is 0: | |
return ls | |
l = len(ls) | |
n = n % factorial(l) | |
(q, r) = divmod(n, factorial(l–1)) | |
x = ls[q] | |
return [x] + perms(r, ls[:q]+ls[q+1:]) | |
def isPerm(a, b): | |
""" | |
Check 'b' is one of permutations of 'a' | |
:type a: int or iterablen | |
:type b: int or iterablen | |
:rtype: bool | |
""" | |
return sorted(str(a)) == sorted(str(b)) | |
def isPalindromic(num): | |
""" | |
Check the given number is palindrome | |
:rtype: bool | |
""" | |
return str(num) == str(num)[::–1] | |
def isPandigital(num, s=9): | |
""" | |
Check the given number is pandigial of s | |
:rtype: bool | |
""" | |
n = str(num) | |
return len(n) == s and not '1234567890'[:s].strip(n) | |
def listPalindromic(k): | |
""" | |
Return a list of palinromic numbers in length k | |
""" | |
if k == 1: | |
return range(1, 10) | |
return [sum([n*(10**i) for n, i in enumerate(([x]+list(ys)+[z]+list(ys)[::–1]+[x]\ | |
if k % 2 | |
else ([x]+list(ys)+list(ys)[::–1]+[x])))]) | |
for x in range(1, 10) | |
for ys in itertools.product(range(10), repeat=k/2–1) | |
for z in (range(10) if k % 2 else (None,)) | |
] | |
def sumOfFactorialDigits(num): | |
sum_ = 0 | |
while num > 0: | |
sum_, num = sum_ + FACT[num % 10], num // 10 | |
return sum_ | |
def fib(n): | |
""" | |
Find the nth number in fibonacci series. | |
>>> fibonacci(100) | |
…. | |
Algorithm & Python source: Copyright (c) 2013 Nayuki Minase | |
Fast doubling Fibonacci algorithm | |
http://nayuki.eigenstate.org/pate/fast-fibonacci-algorithms | |
""" | |
if n < 0: | |
raise ValueError("Negative arguments not implemented") | |
return _fib(n)[0] | |
def _fib(n): | |
if n == 0: | |
return (0, 1) | |
else: | |
a, b = _fib(n//2) | |
c = a * (2 * b – a) | |
d = b * b + a * a | |
if n % 2 == 0: | |
return (c, d) | |
else: | |
return (d, c+d) | |
### —————————————————————————- | |
def gcd(a, b): | |
""" | |
Compute the greatest common divisor of a and b. | |
""" | |
(a, b) = (abs(a), abs(b)) | |
if a == 0: | |
return b | |
while b != 0: | |
a, b = b, a%b | |
return b |