找数字的算法

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()

- Alex Wang

---

如果您在找到质数时将其缓存，那么您对质数的一般测试可以通过缓存运行，直到sqrt(n)，而不是通过所有可能的整数直到该值。 - Dragonthoughts

@Dragonthoughts，看起来原始任务规定“不要使用超过常量大小的内存”（请参见我上面评论中的任务链接）。 - גלעד ברקן

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)

这在我的电脑上不到一分钟就可以完成。

- Cendre

Answer 2

好的，这段代码存在几个问题：

1. You modify the original n at the beginning (n //= 10). This basically causes n to always be one digit. Use another variable instead: m = n while m // 10 > 0: l += 1 m //= 10
2. Your recursive call doesn't update n, so you enter an infinite loop: while n <= maxprime: dominant_prime_finder() Replace with: if n <= maxprime: dominant_prime_finder(maxprime, n + 1)

3. Even after fixing these issues, you'll cause a stack overflow simply because the dominant prime numbers are very far apart (2, 5, 3733, 59399...). So instead of using a recursive approach, use, for example, a generator:

   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())
   

- memo

Answer 3

这个问题很酷。以下是我们如何详细说明递归：

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)

- גלעד ברקן