用Python查找第n个幸运数

Question

我正在尝试用Python编写一个程序，生成第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

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。比如说，可能会有一些错误提示，或者是代码没有按照预期的方式运行。这时候，我们就需要去查找解决方案，通常可以在一些技术论坛上找到答案，比如StackOverflow。

在这些论坛上，很多人会分享他们的经验和解决方法。你可以看到其他人遇到的类似问题，以及他们是如何解决的。这不仅能帮助你解决当前的问题，还能让你学到一些新的知识和技巧。

总之，遇到问题时，不要着急，先去查找一下相关的资料和讨论，通常会有意想不到的收获。

n=input('enter n ')
a= list(xrange(1,n))
x=a[1]
for i in range(1,n):
    del a[x-1::x]
    x=a[i]
    l=len(a)

    if i==l-1:
        break

print "lucky numbers till %d" % n
print a  


lets do this with an example.lets print lucky numbers till 100
put n=100
firstly a=1,2,3,4,5....100
x=a[1]=2
del a[1::2] leaves 
a=1,3,5,7....99
now l=50
and now x=3
then del a[2::3] leaving a =1,3,7,9,13,15,.....
and loop continues till i==l-1

Answer 2

使用numpy数组时，你可以利用布尔索引，这可能会对你有帮助。举个例子：

>>> a = numpy.arange(10)
>>> print a
[0 1 2 3 4 5 6 7 8 9]

>>> print a[a > 3]
[4 5 6 7 8 9]

>>> mask = np.array([True, False, True, False, True, False, True, False, True, False])
>>> print a[mask]
[0 2 4 6 8]

下面是一个使用numpy数组的幸运数字函数：

import numpy as np

class Didnt_Findit(Exception):
    pass

def lucky(n):
    '''Return the nth lucky number.

    n --> int

    returns int
    '''

    # initial seed
    lucky_numbers = [1]
    # how many numbers do you need to get to n?
    candidates = np.arange(1, n*100, 2)
    # use numpy array boolean indexing
    next_lucky = candidates[candidates > lucky_numbers[-1]][0]

    # accumulate lucky numbers till you have n of them
    while next_lucky < candidates[-1]: 
        lucky_numbers.append(next_lucky)
        #print lucky_numbers
        if len(lucky_numbers) == n:
            return lucky_numbers[-1]
        mask_start = next_lucky - 1
        mask_step = next_lucky
        mask = np.array([True] * len(candidates))
        mask[mask_start::mask_step] = False
        #print mask
        candidates = candidates[mask]
        next_lucky = candidates[ candidates > lucky_numbers[-1]][0]
    raise Didnt_Findit('n = ', n)

>>> print lucky(10)
33

>>> print lucky(50)
261

>>> print lucky(500)
3975

我检查了我和@icecrime在10、50和500这几个数字上的输出，结果是一样的。

你的代码运行得比我的快，而且在处理更大数字时表现得更好。

Answer 3

我想出了这个方法，但有没有更好的办法呢？

其实，永远会有更好的办法，剩下的问题是：这个方法对你的需求来说是否“足够好”？

一个可能的改进是把这些内容变成一个生成器函数。这样的话，你只会在需要的时候计算新的值。我想出了这个版本，目前只验证了大约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配方：

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)

我希望这个方法有效，而且毫无疑问，代码还有更多改进的空间（但正如之前所说，总是有改进的空间！）。