오일러 프로젝트의 첫 열 개 문제를 파이썬3로 풀이한 모음이다. 부록으로 오일러프로젝트 문제 풀이에 흔히 사용할 수 있는 “빠르게 동작하는” 함수 몇 가지를 미리 작성하여 덧붙였다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. | |
| 예를 들면 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """소수를 크기 순으로 나열하면 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """다음은 연속된 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """세 자연수 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #-*-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 |