python - 在 Python 中找到筛子生成的第 n 个幸运数字

Question

我正在尝试用 Python 编写一个程序，它将根据 lucky number sieve 生成第 n 个幸运数字.我是 Python 的新手，所以我还不知道该怎么做。到目前为止，我已经想出如何制作一个函数来确定所有低于指定数字的幸运数字:

def lucky(number):
    l = range(1, number + 1, 2)
    i = 1
    while i < len(l):
        del l[l[i] - 1::l[i]]
        i += 1
    return l

有没有办法修改它，以便我可以找到第 n 个幸运数字？我想过逐渐增加指定的数字，直到创建一个长度合适的列表来找到所需的幸运数字，但这似乎是一种非常低效的方法。

编辑:我想到了这个，但有更好的方法吗？

def lucky(number):
    f = 2
    n = number * f
    while True:
        l = range(1, n + 1, 2)
        i = 1
        while i < len(l):
            del l[l[i] - 1::l[i]]
            i += 1
        if len(l) >= number:
            return l[number - 1]
        f += 1
        n = number * f

Answer 1

I came up with this, but is there a better way?

事实是，总会有更好的方法，剩下的问题是:它是否足够好满足您的需求？

一个可能的改进是将所有这些变成一个生成器函数。这样，您只会在使用新值时计算新值。我想出了这个版本，我只验证了大约 60 个术语:

import itertools


def _idx_after_removal(removed_indices, value):
    for removed in removed_indices:
        value -= value / removed
    return value


def _should_be_excluded(removed_indices, value):
    for j in range(len(removed_indices) - 1):
        value_idx = _idx_after_removal(removed_indices[:j + 1], value)
        if value_idx % removed_indices[j + 1] == 0:
            return True
    return False


def lucky():
    yield 1
    removed_indices = [2]
    for i in itertools.count(3, 2):
        if not _should_be_excluded(removed_indices, i):
            yield i
            removed_indices.append(i)
            removed_indices = list(set(removed_indices))
            removed_indices.sort()

如果您想从此生成器中提取第 100 个项，您可以使用 itertools nth recipe :

def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(itertools.islice(iterable, n, None), default)

print nth(lucky(), 100)

我希望这能奏效，而且毫无疑问还有更多的代码改进空间(但如前所述，总是有改进的空间!)。