Я экспериментировал с этой проблемой с тех пор, как вы ее опубликовали. Я не решил это, но хотел бы поделиться тем, что у меня есть, прежде чем перейти к чему-то другому:
Генерация простых чисел Не Проблема
При правильном алгоритме просеивания мы можем сгенерировать все простые числа до 10 ** 6 за долю секунды. (Менее 1/3 секунды на моем Mac mini.) Трата времени на оптимизацию генерации после этого является пустой тратой времени.
Метод грубой силы
Если мы попытаемся сгенерировать все перестановки трех простых чисел в Python, например ::
for prime_1 in primes:
for prime_2 in primes:
if prime_2 < prime_1:
continue
for prime_3 in primes:
if prime_3 < prime_2:
continue
pass
Или, что еще лучше, опустите проблему до уровня C с помощью itertools Python:
from itertools import combinations_with_replacement
for prime_1, prime_2, prime_3 in combinations_with_replacement(primes, 3):
pass
Тогда наши тайминги, не выполняющие никакой реальной работы, кроме генерации простых троек, выглядят так:
sec.
10**2 0.04
10**3 0.13
10**4 37.37
10**5 ?
Вы можете видеть, сколько времени увеличивается с каждым порядком величины. Вот мой пример решения грубой силы:
from itertools import combinations_with_replacement
def sieve_primes(n): # assumes n > 1
sieve = [False, False, True] + [True, False] * ((n - 1) // 2)
p = 3
while p * p <= n:
if sieve[p]:
for i in range(p * p, n + 1, p):
sieve[i] = False
p += 2
return [number for number, isPrime in enumerate(sieve) if isPrime]
primes = sieve_primes(10 ** 3)
print("Finished Sieve:", len(primes), "primes")
special = 0
for prime_1, prime_2, prime_3 in combinations_with_replacement(primes, 3):
if (prime_1 * prime_2 * prime_3) % (prime_1 + prime_2 + prime_3) == 0:
special += 1
print(special)
Избегайте создания троек, но все еще грубой силы
Вот подход, который позволяет избежать генерации троек. Мы берем самые маленькие и самые большие сгенерированные нами простые числа, формируем их кубы и зацикливаем их с помощью пользовательской функции факторинга. Эта пользовательская функция факторинга возвращает значение только для тех чисел, которые состоят из ровно трех основных факторов. Для любого числа, составленного из более или менее, возвращается None. Это должно быть быстрее, чем обычный факторинг, так как функция может сдаться раньше.
Числа, которые делятся ровно на три простых числа, легко проверить на специальность. Мы собираемся сделать вид, что наша пользовательская функция факторинга совсем не требует времени и просто измерить, сколько времени нам потребуется, чтобы перебрать все рассматриваемые числа:
smallest_factor, largest_factor = primes[0], primes[-1]
for number in range(smallest_factor**3, largest_factor**3):
pass
Опять же, время:
sec.
10**2 0.14
10**3 122.39
10**4 ?
Не выглядит многообещающе. На самом деле, хуже, чем наш оригинальный метод грубой силы. А наша пользовательская функция факторинга в реальности добавляет много времени. Вот мой пример этого решения (копия sieve_primes() из предыдущего примера):
def factor_number(n, count):
size = 0
factors = []
for prime in primes:
while size < count and n % prime == 0:
factors.append(prime)
n //= prime
size += 1
if n == 1 or size == count:
break
if n > 1 or size < count:
return None
return factors
primes = sieve_primes(10 ** 3)
print("Finished Sieve:", len(primes), "primes")
special = 0
smallest_factor, largest_factor = primes[0], primes[-1]
for number in range(smallest_factor**3, largest_factor**3):
factors = factor_number(number, 3)
if factors:
if number % sum(factors) == 0:
special += 1
print(special)