Schulhilfe BITTE BITTE!!!!! Problem

[AIMAR009]

Hi habe ein riesen Problem soll als Hausaufgabe verbal (auf Deutsch) aufschreiben wie ich ein Programm Programmiere das die Primzalhen ausgibt zum Schluss. So weit bin ich schon:

Liste anlegen
den Bereich eingeben (z.B alle Primzahlen von 0 bis 50)

und wie gehts weiter das er mir alle primzahlen aus dem Bereich 0-50 zum schluss ausgibt?

Würde mich über Antwort freuen Gurß Aimar

[AIMAR009]

es soll mit zwei schleifen und mit einer auswahl funktionieren wie?

[Dookie]

Hi AIMAR009,

das ist wohl am einfachsten mit dem klassischen "Sieb des Erastothenes" zu lösen. Ich hab im Netz folgendes gefunden:
http://www.ph-cip.uni-koeln.de/~puetsch ... tml#python


Gruß

Dookie

[Dookie]

Noch etwas ausführlicher.

Als erstes würde ich bei der Liste gleich 0 und 1, die ja keine Primzahlen sind weglassen. Also eine Liste mit den Werten von 2-50. Anlegen:

Code: Alles auswählen

prim = range(2,51)

Dann wird der erste Eintrag genommen, dies ist gleichzeitig die erste Primzahl und es werden alle Vielfachen davon aus der Liste entfernt. Dabei brauchen nur die Werte bis Wurzel aus 50 (=50^0.5) durchlaufen werden:

Code: Alles auswählen

for i in xrange(2,50**0.5+1):
    if i in prim: # i ist in der liste also
        for j in xrange(i*2,51,i): #alle vielfachen von i sind keine primzahlen
            if j in prim: #wenn j noch in der Liste,
                prim.remove(j) # aus der Liste löschen

Am Schluss nur noch die Liste ausgeben

Code: Alles auswählen

print prim

fertig.


Gruß

Dookie

[AIMAR009]

Sorry bin erst im ersten Lernjahr. Sorry. Verstehe leider gar ncihts davon. Ich kene nur die befelhe von der auswahl und der schlaeife. Das mit der Wurzel kenne ich ncoh garnicht. Kann man das auch ganz einfach machen nur mit der DIVISION UND MULTIPLIKATION? Würde mich über Antwort freuen

Gruß AIMAR

[Dookie]

jo, die Wurzel ist hier nur eine Optimierung, es geht aber auch ohne.

Hier mal ein ganz simples dokumentiertes Beispiel, ohne Optimierungen und nur mit while-Schleifen und nur mit Additionen.

Code: Alles auswählen

n = input("Bereich eingeben: ") # Bereich festlegen
prim = range(2,n+1) #eine Liste für die Primzahlen von 2 bis n erstellen:

#jetzt den Bereich von 2 bis n durchgehen (1. Schleife) 0 und 1 sind keine Primzahlen!
i = 2
while i <= n:
    if i in prim: # wenn Auswahl (i) in der Liste der Primzahlen
        #lösche alle Vielfachen von i aus der Liste (2. Schleife)
        j = i
        while j < n:
            j = j + i # Vielfaches von i (*2, *3, *4...)
            if j in prim: # ist Vielfaches von i noch in der Liste?
                prim.remove(j) # dann aus der Liste löschen
            # nächstes Vielvaches
    i = i + 1 # nächste Auswahl (i)

#prim enthält jetzt nur noch Primzahlen und kann ausgegeben werden
print prim

Gruß

Dookie

[Milan]

Hi. Tut es nicht auch ein einfacher Test auf Teilbarkeit? Ist vielleicht nicht so effektiv, aber am Anfang leichter verständlich.

Code: Alles auswählen

erglist=[]
MAXPRIM = 10000
for zahl in xrange(2,MAXPRIM+1,1):
    for prim in erglist:
        if zahl%prim==0: break
    else:
        print zahl
        erglist.append(zahl)

Milan

[Dookie]

Hi Milan,

stimmt natürlich. Als Programmierer, stolpert man, wenn man mit einer neuen Programmiersprache anfängt, fasst zwangsläufig auf das Sieb des Erastothenes und vergisst, daß es auch noch anders geht

Ich würd die innere Schleife aber trotzdem aus Performancegründen anders gestalten.

Code: Alles auswählen

if not hasattr(__builtins__,"bool"): # True und False für Python < 2.2
    True = 1
    False = not True

# Bereich festlegen
while 1:
    n = input("Bereich eingeben: ") # Bereich festlegen
    if isinstance(n, type(1)) and n >= 2: # Type und Bereich Testen
        break # Type und Bereich sind ok, also weiter im Text

result = [2]# Liste für Primzahlen 2 ist die erste Primzahl
# wenn wir die 2 nicht gleich in die Liste aufnehmen würden, müssten wir 
# in der Testschleife, für die 2, noch eine Sonderbehandlung einbauen.

for zahl in xrange(3, n+1):
    #den Bereich von 3 bis n durchgehen (1. Schleife)

    # 0 und 1 sind keine Primzahlen!!! 2 ist schon in unserer Liste.

    for prim in result:
        # Testen ob Zahl eine Primzahl ist (2. Schleife)
        # Zahl ist dann keine Primzahl, wenn sie durch eine Primzahl
        # ohne Rest teilbar ist. Wenn die Zahl kleiner als prim*prim ist, 
        # kann sie nicht mehr durch prim ohne Rest geteilt werden und
        # ist somit eine Primzahl
        if prim*prim > zahl: # wenn prim * prim grösser als zu Testende Zahl
            result.append(zahl) # Zahl ist eine Primzahl, in Liste eintragen
            break # Testschleife ist fertig
        if zahl % prim == 0: # Rest der Division = 0
            break # Zahl ist keine Primzahl, Testschleife beenden
            # sonst weiter mit Testschleife -> nächste Primzahl

#prim enthält jetzt alle Primzahlen von 2 bis n und kann ausgegeben werden
print result

@AIMAR009:
der %-Operator liefert den Rest der Division.


Gruß

Dookie

[Milan]

Hi. Naja, war ja auch nur so schnell ausm Ärmel geschüttelt . Aber Wenn schon optimieren, dann richtig:

Code: Alles auswählen

result=[2]
n=10000
for zahl in xrange(3, n+1,2): 
    for prim in result: 
        if prim*prim > zahl:
            result.append(zahl)
            break
        if zahl % prim == 0:
            break

timeit.Timer meint, das wäre gut 20 mal so schnell (hab deines ohne die ganzen Kommentare und so getestet).

Gruß, Milan

[Dookie]

hehe, soll ja hier kein optimierungswettkampf werden, sonst greif ich gleich wieder zum Sieb

AIMAR scheint eh das Interesse verloren zu haben. Naja, wer sich nicht zu fragen Traut, wird irgendwann mal dumm sterben.


Gruß

Dookie

[Milan]

Hi. Ich hab eh gerade nen Fehler verbessert, weswegen meines vermeintliche Siebenmeilenstiefel hatte... Bei mir war nen kleiner Bug drin, weswegen die innere Schleife nie gerufen wurde und dann ist das natürlich verdammt schnell . So stimmts wieder, sind aber nur noch 14% Plus in Geschwindigkeit. Aber du hast auch recht, soll kein Wettbewerb werden, auch wenns sicher Spaß machen würde

Milan

[Leonidas]

Mein kleines Primzahlen Benchmark:

Code: Alles auswählen

import sys
import time

__version__ = "0.0.8"
args = """bench.py (%s) - Small benchmark with primes (Free Software - GPLed)
Credits: Author Leonidas
Commandline arguments:
bench.py [-n<number>|-t<number>|-u<number>|-i<number>] [-b|--benchmark]
  -n<number> : get next prime which is bigger than <number>
  -t<number> : find <number> primes
  -u<number> : find primes until <number>
  -i<number> : check whether <number> is a prime
  -b --benchmark : benchmark results"""

def checkPrime(number):
    """This is the core def, it checks whether
    the number is a prime or not."""
    prime_found = False
    # Some hacks, to return right values
    if number == 0:
        return False
    if number is 1 or number is 2:
        return True
    if number < 0:
        # If number is smaller than zero so use absolute value
        number = abs(number)
    for dividor in xrange(2, number):
        if number % dividor is 0:
            #print "No Prime: %d" % lastprime
            prime_found = False
            return False
        else:
            prime_found = True
    if prime_found is True:
        #print "Prime: %d" % lastprime
        return True
        
def nextPrime(prime_to_test):
    """Returns the next prime"""
    while True:
        prime_to_test = prime_to_test + 1
        #print "ptt==%d" % prime_to_test
        if checkPrime(prime_to_test):
            # Found prime
            #print "Prime==%d" % prime_to_test
            return prime_to_test
            #break
            
def findNumberOfPrimes(primes_to_find):
    """Returns a list of primes
    You have to wait long time without output
    cause it produces no output to stdout
    ToDo: make a starting value"""
    primes_found = 0
    lastnumber = 2
    primes_list = []
    while True:
        if checkPrime(lastnumber):
            primes_list.append(lastnumber)
            primes_found = primes_found + 1
        if primes_found == primes_to_find:
            return primes_list
        lastnumber = lastnumber + 1

def findPrimesUntil(until_number):
    """Finds primes until number N is reached"""
    primes_list = []
    for number in xrange(2, until_number):
        if checkPrime(number):
            primes_list.append(number)
    return primes_list

def main():
    """The main def, which makes this script executable
    PyLint: this def has to many branches, but what to do?"""
    benchmark = False
    if len(sys.argv) == 1: 
        # if no arguments display help
        print args % __version__
        # and exit
        sys.exit(1)
    elif len(sys.argv) == 3:
        # benchmarking on?
        if sys.argv[2][:2] == "-b" or sys.argv[2][:11] == "--benchmark":
            print "Benchmark enabled"
            benchmark = True
        else:
            print "There is no such commandline argument!"
    if sys.argv[1][:2] == "-n":
        # Simply get the next prime
        if benchmark:
            print "There is too less to benchmark"
        prime_to_test = int(sys.argv[1][2:])
        prime_found = nextPrime(prime_to_test)
        print "Prime==%d" % prime_found
    elif sys.argv[1][:2] == "-t":
        until_prime = int(sys.argv[1][2:])
        if benchmark: 
            startTime = time.time()
        primes = findNumberOfPrimes(until_prime)
        if benchmark:
            stopTime = time.time()
            taken = stopTime - startTime
        for prime in primes:
            print "Prime==%d" % prime
        if benchmark: 
            print "Seconds==%G" % taken

    elif sys.argv[1][:2] == "-u":
        until_number = int(sys.argv[1][2:])
        if benchmark: 
            startTime = time.time()
        primes = findPrimesUntil(until_number)
        if benchmark:
            stopTime = time.time()
            taken = stopTime - startTime
        for prime in primes:
            print "Prime==%d" % prime
        if benchmark: 
            print "Seconds==%G" % taken
            
    elif sys.argv[1][:2] == "-i":
        prime_to_check = int(sys.argv[1][2:])
        if benchmark:
            print "There is too less to benchmark"
        result = checkPrime(prime_to_check)
        if result == True:
            print "Prime==True"
        else:
            print "Prime==False"
        
        
            
if __name__ == '__main__':
    main()

Mit pyco geht es sogar rasend schnell.

[Milan]

Hi. Bin gerade in anderem Zusammenhang wieder über den Thread gestolpert und hab was zu meckern: im Code von Leonidas (genauer in checkprime) ist ein kleiner böser Fehler:

Code: Alles auswählen

    if number is 1 or number is 2: 
        return True

Das is ist kritisch! Es werden keine Longs oder Floats erkannt, die aber genau denselben Wert haben, bzw eigene Datentypen, die sich wie Zahlen verhalten. Ich würde unbedingt einen Gleichtstest (==) statt Identitätstest durchführen. Selbes gilt für Verwendung von "is" weiter unten.

[Dookie]

Hi auch nochmal,

im übrigen 1 ist keine Primzahl!


Gruß

Dookie

[Dookie]

gerade drübergestolpert:
http://home.t-online.de/home/primzahl/


Gruß

Dookie

[Leonidas]

Okay, dann habe ich mich geirrt. Ich hab's jezt in meinem Code ausgebessert. Alle machen fehler, oder? Naja, jedenfalls danke für den Tip.