Codewars 中的 Python 解决方案无法通过时间限制，需要优化

Question

有一个关于代码战争的问题，没有素数的生活。我解决了它，但时间问题出现了。我真的找不到更好的方法。说明是这样的;

考虑一个没有素数的数组，并且它的所有元素都没有任何素数。它将以以下开头：[1,4,6,8,9,10,14,16,18,..]。索引 1 处的元素为 4。

将

给出一个整数 n，任务将返回数组中该索引处的数字。例如，solve（1） = 4，如上所述。

这是我的解决方案

def solve(n):
    no_primes=[]
    a=1
    if n == 1:
        return 4
    else:
        while True:
            try:
                no_primes[n]
                break
            except IndexError:
                if is_prime(a) == True:
                    if is_num_prime(a) == False:
                        no_primes.append(a)
                a=a+1
        return no_primes[n]
def is_prime(num):
    numbers = list(map(int, list(str(num))))
    #primes=[0,2,3,5,7,9]
    non_primes=[0,1,4,6,8,9]
    return all(list(map(lambda x:x in non_primes,numbers)))
def is_num_prime(num):
    if num == 2:
        return True
    elif num >2:
        for i in range(2,num):
            if num%i == 0:
                return False
        else:
            return True
    else:
        return False

摆脱 while 循环可能会有所帮助，但我需要继续追加，直到我可以从列表中达到值。使用 n 递归增加的 range(1,n) 递归 for 循环可能是一种选择，但我无论如何都写不出来。

Answer 1

您可以通过简单的步骤轻松分解此问题：

生成所有组合

您可以制作一个无尽的生成器，使这些数字的组合越来越长

def generate_numbers():
    digits= '014689'
    for i in itertools.count(1): # ever longer number
        for x in itertools.product(digits, repeat=i): # combine the digits
            number = ''.join(x)
            if number[0] != '0':
                yield int(number)

print(list(itertools.islice(generate_numbers(), 40)))

[1, 4, 6, 8, 9, 10, 11, 14, 16, 18, 19, 40, 41, 44, 46, 48, 49, 60, 61, 64, 66, 68, 69, 80, 81, 84, 86, 88, 89, 90, 91, 94, 96, 98, 99, 100, 101, 104, 106, 108]

检查数字是否为质数

def is_prime(num):
    if num in {0, 1,}:
        return False
    if num == 2:
        return True
    if not (num % 2):
        return False
    for i in range(3, round(num **.5 + 1), 2):
        if not (num % i):
            return False
    return True

返回第 n 个非质数

def solve(n):
    non_prime_solutions = (i for i in generate_numbers() if not is_prime(i))
    return next(itertools.islice(non_prime_solutions, n, None))

[solve(i) for i in (1, 2, 10, 100)]

[4, 6, 44, 644]

由于所有这些都是懒惰评估的，因此这应该非常快。可以优化的一件事是is_prime

Answer 2

import math
import itertools
def is_prime(n):
    return all(n % i for i in range(2, int(math.sqrt(n) + 1)))
prime_digits = {"2", "3", "5", "7"}
def no_prime_digit(n):
    return not any(x in prime_digits for x in str(n))
def non_primes():
    return (i for i in itertools.count() if no_prime_digit(i) and not is_prime(i))
def get_non_prime(n):
    return next(x for i, x in enumerate(non_primes()) if i == n - 1)
print([(x, get_non_prime(x)) for x in [1, 10, 100]])