Как перечислить наборы панцифровых простых чисел

Недостаток вот в чем. Рассмотрим набор {2,5,47,89,631}. К этому могут привести различные первоначальные расколы. Один {1,2,3,6}, {4,5,7,8,9}, другой {1,3,6,8,9} {2,4,5,7}. Есть еще много других. И поэтому вы пересчитываете.

Чтобы оставить вам удовольствие от проблемы, я не буду рассказывать вам, как исправить этот пересчет. Я просто скажу вам, что если вы считаете несколько способов добраться до определенного набора, то ваше число будет слишком большим.

Это показалось интересным. Чтобы избежать чрезмерного подсчета, я применил рекурсивный подход, основанный на структуре, которая упорядочивает цифры каждого простого кандидата и группирует их по младшей цифре, а также записывает количество каждого набора равных цифр. Например, 13 и 31 будут указаны в группе для младшей цифры 1 как один набор {1, 3} (представленный как битовый набор в виде целого числа) со счетчиком 2.

Затем поиск повторяется по каждому набору цифр, начиная с первой группы, и пытается построить действительные, запомненные пути путем суммирования кратных текущего счетчика со счетчиками для растущих наборов цифр, где следующий выбор делается из группы следующую наименьшую недостающую цифру.

Как я обнаружил, узким местом была генерация только необходимых простых чисел, а не проверка всех простых чисел до 987 654 321.

Выход:

$ python3 prime_sets.py
Creating primes dictionary took 3 seconds.
The answer is 44680.
Recursive search took 0 seconds.

Код Python:

# Project Euler 118
 
import collections
import itertools
import random
import time

 
# https://www.codeproject.com/Articles/691200/Primality-test-algorithms-Prime-test-The-fastest-w
def MillerRabinPrimalityTest(number):
    if number == 2:
        return True
    elif number == 1 or number % 2 == 0:
        return False
 
    oddPartOfNumber = number - 1
    timesTwoDividNumber = 0
 
    while oddPartOfNumber % 2 == 0:
        oddPartOfNumber = oddPartOfNumber // 2
        timesTwoDividNumber = timesTwoDividNumber + 1 
 
    for time in range(3):
        while True:
            randomNumber = random.randint(2, number)-1
            if randomNumber != 0 and randomNumber != 1:
                break
 
        randomNumberWithPower = pow(randomNumber, oddPartOfNumber, number)
 
        if (randomNumberWithPower != 1) and (randomNumberWithPower != number - 1):
            iterationNumber = 1
 
            while (iterationNumber <= timesTwoDividNumber - 1) and (randomNumberWithPower != number - 1):
                randomNumberWithPower = pow(randomNumberWithPower, 2, number)
                iterationNumber = iterationNumber + 1
            if (randomNumberWithPower != (number - 1)):
                return False
 
    return True
 

t0 = time.time()
primes = { d:collections.defaultdict(int) for d in range(1, 10) }

 
def add_prime(p, ps):
  ds = 0
  lowest = 9
  while p > 0:
    d = p % 10
    ds = ds | (1 << d)
    lowest = min(lowest, d)
    p = p // 10
 
  primes[lowest][ds] += 1


for i in range(1, 10):
  for comb in itertools.combinations(map(str, range(1, 10)), i):
    for perm in itertools.permutations(comb):
      n = int("".join(perm))
      if MillerRabinPrimalityTest(n):
        add_prime(n, primes)


t1 = time.time()
print(f"Creating primes dictionary took {int(t1 - t0)} seconds.")


def get_lowest_missing(ds):
  for i in range(1, 10):
    if (1 << i) & ds == 0:
      return i
  return None
 

def f(primes, ds, count, lowest, dp):
  if lowest is None:
    return count
 
  key = (ds, count, lowest)
  if key in dp:
    return dp[key]
 
  answer = 0
 
  for other_ds in primes[lowest]:
    if ds & other_ds == 0:
      answer = answer + f(
          primes,
          ds | other_ds,
          count * primes[lowest][other_ds],
          get_lowest_missing(ds | other_ds),
          dp)
 
  dp[key] = answer
  return answer

 
print(f"The answer is {f(primes, 0, 1, 1, {})}")


t2 = time.time()
print(f"Recursive search took {int(t2 - t1)} seconds.")