Sieb des Eratosthenes Liste mit Wahrheitswerten

[tuxlover]

Hallo,

ich bin neu in diesem Forum und beginne gerade mich mit Python zu beschäftigen. Daher vergebe man mir, falls dieser Thread im falschen Unterforum gelandet ist.

Also folgendes: ich habe eine Liste A mit Zahlen von 2, 100 generiert und möchte dazu eine Liste von Wahrheitswerten generieren, die an i-ter Stelle ein True enthält, falls die Liste A an i-ter Stelle eine Primzahl ist. Andernfalls soll Sie False enthalten. Ich weiß schon dass ich dazu das Sieb des Erasthothenes benötige, damit das eine möglichst geringe Laufzeit hat.

Dies ist mein Programm:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import sqrt

upper_bound = 100
lower_bound = 2 #start with 2 because 1 is never a prime

numbers = []
primes = []
booleans = [True] + [False]*(upper_bound - 2)

#1 generate a list of numbers 1 to upper_bound
for i in range(lower_bound,upper_bound+1,1): 
	numbers.append(i)
j = 2
sqroot = sqrt(upper_bound)
while j**2 <= sqroot:
	if booleans[j-2] == False:
		for k in range((j-2)**2,upper_bound,j):
			booleans[k] = True	
	j += 1 
print(numbers) #for testing purposes
print(booleans)
print(len(numbers))
print(len(booleans)) 

Es kommt leider aber nur Blödsinn heraus. Es wäre nett wenn mir jemand einen kleinen Hinweis dazu geben könnte, wo mein Problem liegt. Möglicherweise geht es auch einfacher, aber ich hier geht es nur darum meinen Fehler zu verstehen, da ich noch neu in Python und im Programmieren bin.

[numerix]

Ein paar Anmerkungen zu deinem Code:

Um eine Liste mit den Zahlen von 1..n zu erstellen, brauchst du keine Schleife aufzusetzen. Es genügt ein:

Code: Alles auswählen

numbers = list(range(1,n+1))

Das math-Modul brauchst du hier nicht. Um die Quadratwurzel von n zu berechnen, kannst du auch über Potenzen gehen:

Code: Alles auswählen

root = n**0.5

Und wenn du über die Wurzel sowieso schon eine obere Grenze berechnest, dann würde ich statt der while-Schleife auch gleich eine for-Schleife verwenden.

Grundsätzlich brauchst du für das Sieb des Eratothenes überhaupt kein Boolesches Feld. Du kannst auch direkt über die Liste der Zahlen iterieren und setzt an den Stellen, wo eine Zahl zu streichen ist, dann eine Null ein.
Am Ende hast du dann in deinem Zahlenfeld nur noch die Primzahlen übrig. Diese kannst du dann entweder über eine Schleife sammeln oder mittels der filter()-Funktion auf einen Schlag die ganzen Nullen herausnehmen.

Wenn du das mal lauffähig hast, könntest du noch etwas optimieren, indem du z.B. von vornherein mit einem Zahlenfeld arbeitest, dass nur die ungeraden Zahlen enthält. Das macht das Sieben ein wenig komplizierter, erhöht aber für größere Siebe die Performance.

[EyDu]

Hallo.

Und dann solltest du dir noch einmal die Bedingung deines "while"s anschauen. Entweder testest du gegen die Wurzel der oberen Grenze oder gegen das Quadrat der aktuellen Zahl. Beides ist ein wenig "ungünstig".

Sebastian

[ms4py]

Um eine Liste mit den Zahlen von 1..n zu erstellen, brauchst du keine Schleife aufzusetzen. Es genügt ein:

Code: Alles auswählen

numbers = list(range(1,n+1))

Warum "list"?!

Code: Alles auswählen

>>> list(range(2,10))
[2, 3, 4, 5, 6, 7, 8, 9]
>>> range(2, 10)
[2, 3, 4, 5, 6, 7, 8, 9]

[Defnull]

Um eine Liste mit den Zahlen von 1..n zu erstellen, brauchst du keine Schleife aufzusetzen. Es genügt ein:

Code: Alles auswählen

numbers = list(range(1,n+1))

Warum "list"?!

Weil `range()` in Python 3 einen Generator und keine Liste zurück gibt und der Fragesteller `print()` als Funktion nutzt, was stark auf Python3 hindeutet.

[ms4py]

Wieder was gelernt
Aber eigentlich hätte ich mir das auch denken können...

[Dav1d]

Eine Lösung von mir, aber nur wenn du "bescheißen" willst Hier

[tuxlover]

Vielen Dank für die netten Hinweise.
Ich habe es jetzt endlich implementiert bekommen. Es funktioniert nun so, dass es für jede nicht Primzahl eine 0 schreibt. Das war schon mal ein brauchbarer Hinweis. Genau wie die anderen Hinweise die ihr mir gegeben habt.
Der Code sieht nun so aus:

Code: Alles auswählen

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from math import sqrt

upper_bound = 100
numbers = list(range(1,upper_bound +1)) #gernerates a list 2,to upperroot 
numbers[0] = 0 #the first entry is 1 which is never a prime 
i = 2
sqroot = sqrt(upper_bound)
while i <= sqroot:
	if numbers[i-1] > 0:  #because we start at 0th possition
		for j in range(i-1+i,upper_bound,i):
			numbers[j] = 0	
	i = i + 1	
print(numbers)

Aber wie ich das in einer for-Schleife implementieren soll, ist mir unklar.
Außerdem gefällt mir noch nicht dass ich prime als extra Variable deklariere und es anschließend zurückschreibe. Vielleicht hat jemand noch einen Hinweis dazu.

^habs korrigiert 1 minute später ist mir eingefällen, dass ich wohl besser i selber einfach in der forschleife überspringe.

[BlackJack]

@tuxlover: Woran hapert es denn, dass Du aus der ``while``-Schleife keine ``for``-Schleife machen kannst? Du willst doch dort eine Schleife über ganze Zahlen von einer Startzahl bis zu einer Endzahl. Beide sind vor Eintritt in die Schleife bekannt. Wie würdest Du denn eine ``for``-Schleife schreiben, die über die Zahlen 1 bis 10 geht? Wenn Du das kannst, musst Du doch nur die festen Grenzen durch die ersetzen, die bei diesem Problem eingesetzt werden müssen.