Книга: Рассказы о математике с примерами на языках Python и C

8. Магический квадрат из простых чисел

8. Магический квадрат из простых чисел

Существует еще одна разновидность магического квадрата — составленного из простых чисел. Пример такого квадрата показан на рисунке:

Приведенную выше программу легко модифицировать для такого расчета: достаточно лишь заменить множество digits = set(range(1, 16 + 1)) на другое, содержащее простые числа.

Для примера будем искать квадраты среди трехзначных простых чисел от 101 до 491. Заменим в предыдущей версии программы строку digits = set([1, 2, 3, 4, 5, 6, 7, 8, 9]) на

primes = [ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
      167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
      257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
      353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
      449, 457, 461, 463, 467, 479, 487, 491 ]
digits = set(primes)

Таких квадратов нашлось 40, например:

Сумма чисел равна вполне красивому числу 789.

Т. к. число вариантов перебора больше, программа работает дольше. Время поиска составило 724 с для Python-версии и 316 c для программы на C++.

T = 316.00s = C++

T = 724.4s = Python

Если же рассматривать минимально возможный квадрат из простых чисел, то его сумма равняется тоже вполне «красивому» числу 111:

Примером квадрата 4х4 может быть квадрат с также «красивой» суммой 222:

Оглавление книги