Finden Sie die n-te Glückszahl, die von einem Sieb in Python generiert wird

Question

Ich versuche, ein Programm in Python zu erstellen, das die n-te Glückszahl gemäß dem Glückszahl-Sieb generiert. Ich bin ziemlich neu in Python, also weiß ich noch nicht, wie ich das alles machen soll. Bisher habe ich herausgefunden, wie ich eine Funktion erstelle, die alle Glückszahlen unterhalb einer bestimmten Zahl bestimmt:

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

Gibt es eine Möglichkeit, dies zu ändern, damit ich stattdessen die n-te Glückszahl finden kann? Ich habe daran gedacht, die angegebene Zahl allmählich zu erhöhen, bis eine Liste der erforderlichen Länge erstellt wurde, um die benötigte Glückszahl zu finden, aber das scheint wie eine wirklich ineffiziente Möglichkeit zu sein.

Bearbeiten: Ich habe das herausgefunden, aber gibt es einen besseren Weg?

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

Ich habe das hier entwickelt, aber gibt es einen besseren Weg?

Die Wahrheit ist, es wird immer einen besseren Weg geben, die entscheidende Frage ist: ist es gut genug für Ihre Bedürfnisse?

Eine mögliche Verbesserung wäre, all dies in eine Generatorfunktion umzuwandeln. Auf diese Weise würden nur neue Werte berechnet, wenn sie verbraucht werden. Diese Version habe ich entwickelt, die ich nur bis zu etwa 60 Begriffe validiert habe:

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

Wenn Sie beispielsweise den 100. Begriff aus diesem Generator extrahieren möchten, können Sie das itertools nth recipe verwenden:

def nth(iterable, n, default=None):
    "Gibt das n-te Element oder einen Standardwert zurück"
    return next(itertools.islice(iterable, n, None), default)

print nth(lucky(), 100)

Ich hoffe, dass dies funktioniert, und es gibt ohne Zweifel noch mehr Raum für Codeverbesserungen (aber wie bereits erwähnt, es gibt immer Raum für Verbesserungen!).

Answer 2

Mit NumPy-Arrays können Sie die boolesche Indizierung verwenden, was hilfreich sein kann. Zum Beispiel:

>>> 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]

Hier ist eine Glückszahlenfunktion mit Verwendung von NumPy-Arrays:

import numpy as np

class Didnt_Findit(Exception):
    pass

def lucky(n):
    '''Gibt die n-te Glückszahl zurück.

    n --> int

    gibt int zurück
    '''

    # Initialwert
    lucky_numbers = [1]
    # Wie viele Zahlen benötigen Sie, um zu n zu gelangen?
    candidates = np.arange(1, n*100, 2)
    # Verwenden Sie die boolesche Indizierung des NumPy-Arrays
    next_lucky = candidates[candidates > lucky_numbers[-1]][0]

    # Sammle Glückszahlen, bis Sie n davon haben
    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

Ich habe meine und @icecrime's Ausgabe für 10, 50 und 500 überprüft - sie stimmten überein.

Deine Funktion ist viel schneller als meine und skaliert besser mit n.

Answer 3

n=input('Geben Sie n ein ')
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 "Glückszahlen bis %d" % n
print a  

Lassen Sie uns dies anhand eines Beispiels tun. Lassen Sie uns Glückszahlen bis 100 drucken.
Setzen Sie n=100
Zuerst a=1,2,3,4,5....100
x=a[1]=2
löschen Sie a[1::2], lassen Sie
a=1,3,5,7....99
jetzt ist l=50
und jetzt ist x=3
dann löschen Sie a[2::3], lassen Sie a =1,3,7,9,13,15,.....
und die Schleife läuft weiter, bis i==l-1