Алгоритм нахождения чисел

Question

Напишите рекурсивный алгоритм, который перечисляет доминирующие простые числа. Ваш алгоритм должен печатать доминантные простые числа по мере их нахождения (а не в конце). По умолчанию мы ограничиваем доминантные простые числа, которые мы ищем, максимальным значением 10 ^ 12, ожидаемое время выполнения должно быть около или меньше минуты .

Ниже приведен мой код на Python, который не работает должным образом:

import math
def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)


def dominant_prime_finder(maxprime=10**12,n=1):
    l = 1    #length of the current number
    while n // 10 > 0:
        l += 1
        n //= 10
    if test_prime(n) == True:
        is_dominant_prime = True
        index_smaller = n
        while l > 1 and index_smaller > 9:
            index_smaller //= 10
            if test_prime(index_smaller) == False:
                is_dominant_prime = False
                break
        for i in range(1,10):
            if test_prime(i*10**l + n) == True:
                is_dominant_prime = False
                break
        if is_dominant_prime == True:
            print(n)
    while n <= maxprime:
        dominant_prime_finder()

Answer 1

Вы можете решить проблему, не перечисляя все числа до 10 ^ 12, что неэффективно, выполнив рекурсию по длине числа.

Работает следующим образом:

• Простое число длины 1: 2,3,5,7.
• Для всех этих чисел проверьте третье условие, для любой цифры dn+1∈{1,…,9}, dn+1dn…d0 не является простым. Для 2 это нормально. Для 3 это не удается (13, например). Сохраните все найденные простые числа в списке L. Сделайте это для всех простых чисел длины 1.
• В L теперь у вас есть все простое число длины 2 с простым числом в качестве первой цифры, поэтому у вас есть все кандидаты на доминантное простое число длины 2

Выполнение этого рекурсивно дает вам все доминирующие простые числа в python:

def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)

def check_add_digit(number,length):
    res = []
    for i in range(1,10):
        if test_prime( i*10**(length) + number ):
            res.append(i*10**(length) + number)
    return res

def one_step(list_prime,length): 
    ## Under 10^12 
    if length > 12:
        return None

    for prime in list_prime: 

        res = check_add_digit(prime,length)

        if len(res) == 0:
            #We have a dominant prime stop 
            print(prime)
        else:
            #We do not have a dominant prime but a list of candidates for length +1
            one_step(res,length+1)

one_step([2,3,5,7], length=1)

Это работает менее чем за минуту на моей машине.

Answer 2

Эта проблема крутая. Вот как мы можем разработать повторение:

def dominant_prime_finder(maxprime=10**12):
  def f(n):
    if n > maxprime:
      return

    is_dominant = True
    power = 10**(math.floor(math.log(n, 10)) + 1)

    for d in xrange(1, 10):
      candidate = d * power + n

      if test_prime(candidate):
        f(candidate)
        is_dominant = False

    if is_dominant:
      print int(n)

  for i in [2,3,5,7]: 
    f(i)

Answer 3

Ну, есть несколько проблем с этим кодом:

1. Вы изменяете оригинал n в начале (n //= 10). Это в основном заставляет n всегда быть одной цифрой. Вместо этого используйте другую переменную: m = n while m // 10 > 0: l += 1 m //= 10
2. Ваш рекурсивный вызов не обновляет n, поэтому вы входите в бесконечный цикл: while n <= maxprime: dominant_prime_finder() Заменить: if n <= maxprime: dominant_prime_finder(maxprime, n + 1)

3. Даже после исправления этих проблем вы будете вызывать переполнение стека просто потому, что доминирующие простые числа находятся очень далеко друг от друга (2, 5, 3733, 59399 ...). Поэтому вместо рекурсивного подхода используйте, например, генератор:

   def dominant_prime_finder(n=1):
   while True:
       l = 1    #length of the current number
       m = n
       while m // 10 > 0:
           l += 1
           m //= 10
       if test_prime(n):
           is_dominant_prime = True
           index_smaller = n
           while l > 1 and index_smaller > 9:
               index_smaller //= 10
               if not test_prime(index_smaller):
                   is_dominant_prime = False
                   break
           for i in range(1,10):
               if test_prime(i*10**l + n):
                   is_dominant_prime = False
                   break
           if is_dominant_prime:
               yield n
       n = n + 1
   
   g = dominant_prime_finder()
   
   for i in range(1, 10):  # find first 10 dominant primes
       print(g.next())