プロジェクトオイラー8
プロジェクトオイラーの問題8をpythonで解きました。
問題
data = [input() for i in range(20)] joined_data = ''.join(data) i = 0 max_list = [] while i < 987: if '0' in joined_data[i:i+13]: i += 1 continue else: product_number = 1 for num in joined_data[i:i+13]: product_number = product_number * int(num) max_list.append(product_number) i += 1 maximum = max(max_list) print(maximum)
プロジェクトオイラー7
プロジェクトオイラーの7をpythonで解きました。
問題
10001番目の素数を求めよ。
mport math def primes(M): #エラトステネスのふるい prime_true_false = [1] * M prime_true_false[0] = 0 prime_true_false[1] = 0 for number in range(2, int(math.sqrt(M)) + 1): if prime_true_false[number]: for multiple in range(number * number, M, number): prime_true_false[multiple] = 0 return [prime for prime in range(2, M) if prime_true_false[prime] ] print(primes(1000000)[10000])
プロジェクトオイラー2A
プロジェクトオイラーの2の別解です。
友人にはやいやつを教えてもらったので実行してみました。
'''フィボナッチ数列の400万未満の偶数値の和''' a = 1 b = 1 c = 2 even_sum = 0 while a < 4000000: a = b b = c c = a + b if c % 2 ==0: even_sum += <s>a</s> c print(even_sum)
プロジェクトオイラー6
プロジェクトオイラーの問題6をpythonで解きました。
問題
1から100までの和の2乗- 1から100までの2乗和を計算する。
input_list = [number for number in range(1, 101)] #1から100までの数字のリスト sumsquared = int(sum(input_list) ** 2) #1から100までの和の2乗 squared_input_list = [] for number in input_list: squared_input_list.append(number * number) squaredsum = sum(squared_input_list) #1から100までの2乗の和 print(sumsquared) print(squaredsum) print(sumsquared - squaredsum)
プロジェクトオイラー4
プロジェクトオイラーの問題4をpythonで解きました。
問題
3桁の自然数×3桁の自然数で回文数(palindrome)になる数字の中で、最も大きい数字を求めよ。
def palindrome(n): #palindrome関数 from collections import deque dq = deque(n) while len(dq) > 1: if dq.popleft() != dq.pop(): return False return True rows = range(100, 999) cols = range(100, 999) matrix = [(row, col) for row in rows for col in cols if row >= col] palindromes_list =[] for element in matrix: #3桁×3桁のpalindromeのリスト number = element[0] * element[1] if palindrome(str(number)): palindromes_list.append(number) answer = max(palindromes_list) #3桁×3桁でのpalindromeで最大のもの print(answer)
プロジェクトオイラー3
プロジェクトオイラーの問題3を解いてみました。
問題
600851475143の素因数で最も大きい数字はなあに?
最初に書いたコードはこうでした。
N = int(input()) #自然数N def primes(N): #自然数Nまでの素数のリストを作る prime_list = [2] i = 2 while i < N + 1: counter = 0 for prime in prime_list: if i % prime != 0: counter += 1 if counter == len(prime_list): prime_list.append(i) i += 2 return prime_list print(primes(N)[-1]) def prime_factors(N): #自然数Mを素因数分解する(重複無視) factors_list = [] for prime in primes(N): #ここまで大きく取る必要はない if N % prime == 0: factors_list.append(prime) return factors_list def maximum_prime_factor(N): #自然数Nの素因数の中で最大のものを求める return prime_factors(N)[-1] print(maximum_prime_factor(N))
むっちゃ無駄が多いんですが、まあ一応合ってるはずだし答えはでるよな〜って思ってました。ところが、30分たったところでKillされました。
そこでまずはエラトステネスのふるいを実装して、次に、素数生成を必要最低限まで減らすことにしました。それでできたのがこれ
import math N = int(input()) M = int(math.sqrt(N)) + 1 def primes(M): #エラトステネスのふるい prime_true_false = [1] * M prime_true_false[0] = 0 prime_true_false[1] = 0 for number in range(2, int(math.sqrt(M)) + 1): if prime_true_false[number]: for multiple in range(number * number, M, number): prime_true_false[multiple] = 0 return [prime for prime in range(2, M) if prime_true_false[prime] ] def prime_factors(N): #自然数Nを素因数分解する(重複無視) factors_list = [] for prime in primes(M): if N % prime == 0: factors_list.append(prime) return factors_list answer_list = prime_factors(N) print(answer_list) print(answer_list[-1])
N =600851475143 として1秒かからずにできたよ、ヤッタネ。
プロジェクトオイラー2
プロジェクトオイラーの2問目をpythonを使って解いてみました。
問題
フィボナッチ数列の値で4百万を超えない値の、偶数値の総和を求めよ。
下のMに4000000を代入すれば答えが出ます。
M = int(input()) #フィボナッチ数列の値の上限 def fibonacci(n): #フィボナッチ数列の第n番目の項 fib_numbers = [1, 1] if n == 1: return 1 else: while len(fib_numbers) < n + 1: p = len(fib_numbers) - 2 q = len(fib_numbers) - 1 fib = fib_numbers[p] + fib_numbers[q] fib_numbers.append(fib) return fib_numbers[len(fib_numbers) - 1] start = 1 #フィボナッチ数列の1番目の項から始めた sum_of_evenfibonacci = 0 N = 1 while N <= M: #フィボナッチ数列の値がMを超えないもののなかで、偶数値のものだけ和を取った if N % 2 == 0: sum_of_evenfibonacci += N start += 1 N = fibonacci(start) print(sum_of_evenfibonacci)