Проект Эйлера на Python

Условие задачи Сумма простых чисел меньше 10 - это 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов. Решение Мы уже использовали алгоритмы поиска простых чисел на python здесь и здесь . Но в этой задаче я хочу попробовать нечто новое - Решето Эратосфена  . Это достаточно интересный и быстрый алгоритм, но я его не использовал в прошлых задачах т.к они не сильно подходили под условия - здесь же решето Эратосфена подходит практически идеально.

Условие задачи: Тройка Пифагора - три натуральных числа  a  <  b  <  c , для которых выполняется равенство a 2  +  b 2  =  c 2 Например, 3 2  + 4 2  = 9 + 16 = 25 = 5 2 . Существует только одна тройка Пифагора, для которой  a  +  b  +  c  = 1000. Найдите произведение  abc . Решение: Первые формулы зависимостей троек Пифагора известны из трудов  Эвклида 2100 г до н.э, самая известная из них:             a   = 2 mn ,   b   =   m 2   −   n 2 ,   c   =   m 2   +   n 2   ,   m   >   n Ну что же, попробуем ее реализовать в коде.

Условие Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 071984038509624554443629812309878

Условие задачи: Сумма квадратов первых десяти натуральных чисел 1 2  + 2 2  + ... + 10 2  = 385 Квадрат суммы первых десяти натуральных чисел (1 + 2 + ... + 10) 2  = 55 2  = 3025 Следовательно, разность между суммой квадратов и квадратом суммы первых десяти натуральных чисел составляет 3025 − 385 = 2640. Найдите разность между суммой квадратов и квадратом суммы первых ста натуральных чисел. Решение: Для оптимизации будем использовать формулу квадрата суммы из школьной арифметики: ( a + b )   2 = a   2 + 2 a b + b   2

Условие задачи     Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число - 13.     Какое число является 10001-ым простым числом?     Принцип ее решения очень похож на Задачу 3 (наибольший простой делитель), но ограничением будет выступать не само число, а количество чисел в словаре.  Решение     Для начала определим функцию определения простого числа: def issimple(n):     r=math.ceil(math.sqrt(n))     for i in range(2,n):         if n%i==0:             return False     return True     Здесь аналогично задаче 3 - для оптимизации перебираем числа до квадратного корня искомого числа. Если n делится на хотя бы одно число от 2-х до корня n возвращаем false. Иначе True Приведу полный оптимизированный текст: import math def issimple(n):     r=math.ceil(math.sqrt(n))     for i in range(2,n):         if n%i==0:             return False     return True n=5 s=[2,3] while True:     if issimple(

Условие задачи 2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число  делится нацело  на все числа от 1 до 20? Скажу сразу - не смотря на не большой диапазон чисел условия реализация этой задачи получилась громоздкой и ее выполнение занимает больше всего времени - около 90 с  несмотря на все попытки оптимизации. Решение 

Условие задачи Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99. Найдите самый большой палиндром, полученный умножением двух трёхзначных чисел. Заметка. Обычно перед решением каждой задачи я обращаюсь к математическим формулам для поиска оптимального алгоритма, но данную задачу я решил в лоб без особой математической базы. Работает медленно, но меньше 1-й минуты что удовлетворяет основному принципу решения. Решение

Условие задачи Простые делители числа 13195 - это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом? Решение Простым числом, является натуральное число больше единицы, которое имеет 2 делителя - 1 и само себя.  Для начала найдем все простые делители необходимого числа.  Чтобы сократить поиск будем перебирать до квадратного корня  600851475143 округленного вверх  ( функцией  math.ceil) Перебор будем вести начиная с числа 3. Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i. Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143  Код Python import math def issimple(a): r=math.ceil(math.sqrt(a)) lst=[] for i in range(3,r): if a%i==0: if issimple(i)==[]: lst.app

Задача 2  Четные числа Фибоначчи Каждый следующий элемент ряда Фибоначчи получается при сложении двух предыдущих. Начиная с 1 и 2, первые 10 элементов будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Найдите сумму всех четных элементов ряда Фибоначчи, которые не превышают четыре миллиона. Решение на Python Пока не особо владею приемами функционального программирования на Python, но кое-какие шаблонные фитчи использую. Прошу строго не судить о коде: f=[1,2] i=2 a=0 while f[i]<4000000:     f.append(f[i-1]+f[i-2])     i+=1     a=f[i] res=filter(lambda x:x%2==0, f) print(sum(res)) Цикл создающий числа Фибоначчи на основе перебора элементов списка я позаимствовал из Википедии, немного видоизменив под задачу - вместо порога по количеству чисел я установил порог по значению в 4000000. Но данный цикл имеет недостаток- он создает одно число, которое больше установленного порога - 5702887, но оно является не четным и на результат не влияет.  Переменная i х

 . Задача №1 Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел - 23. Найдите сумму всех чисел меньше 1000, кратных 3 или 5. Решение