Unvollständige Probedivision

Neue Frage »

ichwarneu Auf diesen Beitrag antworten »
Unvollständige Probedivision
Hallo zusammen,

ich überlege mir gerade, wie ich die Probedivision mit einer vorgegebenen Obergrenze implementieren kann.
Meine Idee ist folgende:
Hat eine natürliche Zahl keinen Teiler , so ist sie prim.
Ich prüfe also alle Primzahlen bis zu dieser Grenze. Ist die Primzahl ein Teiler, so bilde ich und prüfe mit dem so entstandenen Restfaktoren weiter.
Liegt schlussendlich vor, so ist die Faktorisierung abgeschlossen.
Gilt , so ist der nun vorliegende Rest prim.
Gebe ich nun eine niedrigere Obergrenze vor, so kann ich im Allgemeinen nicht mehr entscheiden, ob der "letzte Restfaktor " prim ist. Es könnte ja eine zusammengesetzt Zahl zein, deren Primfaktoren aber vor meiner Obergrenze kommen.

Nun hänge ich aber an folgendem Problem:
Sei . Dann muss ich die Primzahlen prüfen.
Diese teilen 97 jeweils nicht, also muss 97 eine Primzahl sein.
Ohne dieses Wissen gebe ich nun als Obergrenze vor. So erhalte ich ebenfalls die gleichen, zu prüfenden Primzahlen.
Nun ist , also müsste ich an dieser Stelle ja sagen dass ich nicht weiß, ob 97 prim ist, denn ich weiß ja ebensowenig, dass ich mit die gleichen Primzahlen gefunden hätte.

Ich habe das mal algorithmisch aufgeschrieben:
[attach]53675[/attach]
Dieser Algo liefert mir bei Eingabe 97 mit Obergrenze trotzdem die Aussage, dass 97 eventuell nicht prim ist.

Da frage ich mich: Kann ich mit einer anderen Obergrenze die Primalität überhaupt entscheiden?
HAL 9000 Auf diesen Beitrag antworten »
RE: Unvollständige Probedivision
Zitat:
Original von ichwarneu
Ohne dieses Wissen gebe ich nun als Obergrenze vor.

Wie kommst du denn auf diesen seltsamen Exponenten??? Erstaunt1

Zitat:
Original von ichwarneu
Nun ist , also müsste ich an dieser Stelle ja sagen dass ich nicht weiß, ob 97 prim ist

Es geht nicht darum, dass ist, sondern dass für die nächste Primzahl dann gilt.


Dein Algorithmus enthält übrigens einen gravierenden Fehler: Die Zeilen 19 und 21 müssen nach der Zeile 22 angeordnet werden, die Zeile 20 kann ersatzlos gestrichen werden.
ichwarneu Auf diesen Beitrag antworten »
RE: Unvollständige Probedivision
Zitat:
Original von HAL 9000
Zitat:
Original von ichwarneu
Ohne dieses Wissen gebe ich nun als Obergrenze vor.

Wie kommst du denn auf diesen seltsamen Exponenten??? Erstaunt1


Ich wollte eine Grenze haben, die so beschaffen ist, dass sie mir die gleichen Primzahlen ausgibt wie bei als Obergrenze. Mit der dritten Wurzel wäre das schon nicht mehr gelungen.


Zitat:
Original von HAL 9000
Es geht nicht darum, dass ist, sondern dass für die nächste Primzahl dann gilt.


Das heißt aber doch, dass es bei einer niedrigeren Obergrenze als der Quadratwurzel eben nicht mehr genügt, nur die Primzahlen bis zu dieser Grenze zu überprüfen.
Ich müsste ja dann, wie von dir angemerkt, noch eine Primzahl weiter gehen, um das zu überprüfen.
Sehe ich das richtig?

Falls ja hätte das für mich die Auswirkungen dass ich im Algorithmus entweder überprüfe, ob die Obergrenze mindestens die Quadratwurzel ist, Wenn ja, brauche ich im Fall keine weitere Überprüfung mehr.
Sollte die Grenze kleiner sein, muss ich (mindestens) eine Primzahl weiter gehen.

Vielleicht nochmal ein anderer Gedanke zu dieser Aussage:
Zitat:
Original von HAL 9000
Es geht nicht darum, dass ist, sondern dass für die nächste Primzahl dann gilt.

Falls ich die Quadratwurzel als Obergrenze nehme, weiß ich aber, dass ich nicht weitergehen muss. Denn jede kommende Primzahl wäre ohnehin größer.
Deine Aussage trifft meines Verständnisses nach "nur" den Fall, dass ich eben eine kleinere Grenze gewählt habe.

Deinen Edit zu den Zeilen 19 und 21 habe ich gesehen und schaue da gerade bei.
HAL 9000 Auf diesen Beitrag antworten »
RE: Unvollständige Probedivision
Zitat:
Original von ichwarneu
Ich müsste ja dann, wie von dir angemerkt, noch eine Primzahl weiter gehen, um das zu überprüfen.
Sehe ich das richtig?

Wenn man den falschen Schluss des Algorithmus (siehe mein EDIT) korrigiert, ist das nicht nötig.
ichwarneu Auf diesen Beitrag antworten »

HAL, jetzt hast du im gleichen Moment eine Antwort geliefert, in der ich meine editiert habe Big Laugh
Danke für deine Zeit an dieser Stelle, hoffe das geht jetzt nicht allzu durcheinander in der Diskussion.
Ich frage mich, warum kann ich Zeile 20 streichen?
Der Hintergedanke war - das hätte ich sicherlich anmerken sollen- das mir der Algorithmus eine eventuell unvollständige Liste markiert.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
Ich frage mich, warum kann ich Zeile 20 streichen?

Was soll das mit dem "FALSE" ? Die Prozedur soll eine Liste der Primfaktorzerlegung liefern, und das tut sie auch so. Im Extremfall n=1 liefert sie eine leere Liste zurück, und das ist ja auch Ok.
 
 
ichwarneu Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von ichwarneu
Ich frage mich, warum kann ich Zeile 20 streichen?

Was soll das mit dem "FALSE" ? Die Prozedur soll eine Liste der Primfaktorzerlegung liefern, und das tut sie auch so. Im Extremfall n=1 liefert sie eine leere Liste zurück, und das ist ja auch Ok.


Sie soll mir aber auch sagen, dass die Zerlegung eventuell unvollständig ist.
Ich habe deine Anmerkungen bezüglich der zu vertauschenden Zeilen umgesetzt.
Nun wähle ich die Zahl .
Die Eingabe trialdiv(n, 2) liefert die natürlich vollständige Zerlegung
Zitat:
[[(3, 1), (5, 1), (97, 1), (101, 1)]]
.
Die Eingabe trialdiv(n, 3) hingegen liefert
Zitat:
[(3, 1), (5, 1), (9797, 1)]
.

Nun sollte mir die Ausgabe in irgendeiner Weise zu verstehen geben, dass die Zerlegung unvollständig ist. Daher das FALSE.

Vielleicht ist aber mein Gedanke dahingehend falsch und Grund für diesen Thread.
Ist es nur möglich, die vollständige Zerlegung zu "erkennen" ?
HAL 9000 Auf diesen Beitrag antworten »

Das hatte ich gar nicht auf dem Schirm - ich dachte, in Zeile 2 steht eine Quadratwurzel. Meine 50+Augen haben erst in mehrfacher Vergrößerung entdeckt, dass da statt steht. (Zumal in deinem Erklärtext nirgendwo auch nur dieses erwähnt wurde.) Augenzwinkern

Im Fall ist jedenfalls klar, dass die Primfaktorzerlegung vollständig ist und damit nichts fehlt.

Für kann das mit dem FALSE Sinn machen: Das deutet dann an, dass der letzte Eintrag vorher nicht notwendig eine Primzahl ist.
ichwarneu Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Das hatte ich gar nicht auf dem Schirm - ich dachte, in Zeile 2 steht eine Quadratwurzel. Meine 50+Augen haben erst in mehrfacher Vergrößerung entdeckt, dass da statt steht. Augenzwinkern


Du hast vollkommen recht, das ist sehr leicht zu übersehen. Das sind natürlich Dinge die man als Verfasser gar nicht mehr beachtet. Man weiß ja, da steht das g.

Edit: Ich glaube jetzt verstehe ich auch deinen "Extremfall n==1".
In meinem Algorithmus bedeutet das ja "vollständige Zerlegung". Idealerweise passiert diese natürlich auch bei einer anderen Obergrenze. Wie mir aber mittlerweile scheint, ist das der einzige Fall, den ich mit wirklich eindeutig angeben kann.
ichwarneu Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Für kann das mit dem FALSE Sinn machen: Das deutet dann an, dass der letzte Eintrag vorher nicht notwendig eine Primzahl ist.


Genau.
Leider führt meine aktuelle Umsetzung dazu, dass 97 ebenfalls mit FALSE markiert wird.
Mein Ausweg wäre, dass ich diese Markierung nur im Falle setze, falls nicht auftreten sollte.
Ich fand das bisher etwas unbefriedigend. Aber dein erster Hinweis passt dahingehend vielleicht doch, denn bei weiß ich, dass alle Primzahlen die überhaupt infrage kommen (gesiebt mit Eratosthenes) vorliegen.
Meine Vermutung ist, dass ich das im Falle nicht mehr entscheiden kann und mir das einen Strich durch die Rechnung macht.
ichwarneu Auf diesen Beitrag antworten »

Ich ändere den Algorithmus nach meiner Mittagspause entsprechend ab und würde mich über Rückmeldung wieder freuen smile

Danke bisher für die Zeit und die Antworten!

Meine Implementation in python sieht übrigens bisher so aus: (Kann ich hier im Board auch Code einfügen? )

import math

def eratosthenes(n):
primes = []
for i in range(2, n+1): primes.append(i)
i = 0
p = 2
while p<=math.floor((n+1) / 2):
j = 2
p = primes[i]
if p != 0:
while j * p <= n:
primes[j*p-2] = 0
j = j + 1
i = i + 1
else: i = i + 1
primes = sorted(list(dict.fromkeys(primes)))
if 0 in primes: del primes[0]
return primes

def trialdiv(n, lim = 2):
limit = pow(n, 1/lim)
primes = eratosthenes(math.ceil(limit))
teiler = []
for p in primes:
if n % p == 0:
vielfachheit = 0
while n % p == 0:
vielfachheit = vielfachheit + 1
n = n // p
teiler.append((p,vielfachheit))
if n == 1: return teiler
if p**2 > n:
teiler.append((n,1))
return teiler
if lim>2:
teiler.append((n,1))
teiler.append(False)
if teiler == []: return [(n,1)]
return teiler
HAL 9000 Auf diesen Beitrag antworten »

Der Schluss

code:
1:
2:
3:
4:
5:
    if lim>2:
        teiler.append((n,1))
        teiler.append(False)
    if teiler == []:    return [(n,1)]
    return teiler
ist vermutlich richtig, da man eh nur dahinten hin gelangt, wenn die Liste vorher leer war. Ich hätte es durch das einfachere

code:
1:
2:
3:
4:
    teiler.append((n,1))
    if lim>2:
        teiler.append(False)
    return teiler
ersetzt.
ichwarneu Auf diesen Beitrag antworten »

Das habe ich so nun umgesetzt. Vielen Dank für deine Hilfe, HAL.
Um den code-Tag mal auszuprobieren, hier mein vollständiger Code Augenzwinkern

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
import math

def eratosthenes(n):
    primes = []
    for i in range(2, n+1): primes.append(i)
    i = 0
    p = 2
    while p<=math.floor((n+1) / 2):
        j = 2
        p = primes[i]
        if p != 0:
            while j * p <= n:
                primes[j*p-2] = 0
                j = j + 1
            i = i + 1
        else:   i = i + 1
    primes = sorted(list(dict.fromkeys(primes)))
    if 0 in primes: del primes[0]
    return primes

def trialdiv(n, g = 2):
    limit = math.floor(pow(n, 1/g))
    if g <2:  limit = pow(n, 1/2)
    primes = eratosthenes(limit)
    teiler = []
    for p in primes:
        if n % p == 0:
            vielfachheit = 0
            while n % p == 0:
                vielfachheit = vielfachheit + 1
                n = n // p
            teiler.append((p,vielfachheit))
        if n == 1:  return teiler
        if p**2 > n:
            teiler.append((n,1))
            return teiler
    teiler.append((n,1))
    if g>2:   teiler.append(False)
    return teiler
HAL 9000 Auf diesen Beitrag antworten »

Ich hab ja immer auch ein wenig die Effizienz im Blick. Und da frage ich mich bei deiner Prozedur "eratosthenes":

Muss das wirklich sein, dass du in Zeile 17 einen kompletten Sortier-Algorithmus (Aufwand ) auf dein Feld primes loslässt? Das Feld besteht doch schon ausschließlich aus Nullen sowie dazwischen übriggeblieben die paar schon geordneten Primzahlen! Ist für mich der reinste Overkill: Die Primzahlen aus diesem Feld aufzulesen lässt sich auch ohne erneutes Sortieren problemlos mit Aufwand bewältigen.

Mein Vorschlag wäre da
code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
def eratosthenes(n):
    n1 = int((n+1)/2)
    flag = [1 for p1 in range(0,n1)]
    p1 = 1
    q1 = 4
    while (q1 < n1):
        if (flag[p1] > 0):
            p = 2*p1+1
            r1 = q1
            while (r1 < n1):
                flag[r1] = 0
                r1 += p
        p1 += 1
        q1 += 4*p1
    return [2] + [2*p1+1 for p1 in range(1,n1) if flag[p1] > 0]
ichwarneu Auf diesen Beitrag antworten »

Danke für deinen Hinweis.

Leider bin ich mit python noch nicht so sehr vertraut. Das Siebverfahren war daher mal eine Fingerübung, von der ich allerdings bezüglich Optimalität ebensowenig überzeugt bin.
Gleich werde ich aber deinen Vorschlag mal umsetzen! smile
HAL 9000 Auf diesen Beitrag antworten »

Naja, du solltest es nur übernehmen wenn du verstehst, was ich da tue:

Element flag[i] kennzeichnet NICHT Zahl , sondern die ungerade Zahl , d.h., die geraden Zahlen lasse ich von vornherein außen vor. Außerdem beginne ich pro Primzahl erst mit dem Streichen der Zahl , dann , usw. - das reicht, da alle kleineren Vielfachen von eh schon vorher gestrichen wurden.
ichwarneu Auf diesen Beitrag antworten »

Ok, danke schonmal für die Erklärung.
Ich wollte mir den Algorithmus dann nochmal genauer anschauen und gleichzeitig die Umsetzung in Python damit einüben. Flag wäre da das erste, das ich mir in der Doku nochmal anschaue Augenzwinkern
RavenOnJ Auf diesen Beitrag antworten »

@HAL9000

Ich bekomme bis n=8 in deinem Sieb 'None' als Ergebnis. Schlage deswegen eine alternative Implementierung vor:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
import math

# generates all primes <= n
def eratosthenes(n):
	if n<2:
		return []
	if n==2:
		return [2]
		
	r = int((n-1)/2)
	ns = [1 for x in range(0, r)]
	lim = int((math.sqrt(n+1)-3)/2)+1

	for x in range(0, lim):
		if ns[x] > 0: 
			k = 2*x+3
			k2 = 2*k
		# we begin at k^2 as every lower
		# non-prime is already eliminated	
			q = k*k
			i = int(q/2) - 1
		
			while q <= n:
				ns[i] = 0
				i = i + k
				q = q + k2
		
	return [2] + [2*x+3 for x in range(0,r) if ns[x] > 0]	


Edit: Ziehe meinen Einwand zurück und behaupte das Gegenteil smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
@HAL9000

Ich bekomme bis n=8 in deinem Sieb 'None' als Ergebnis.

Dann hast du ein anderes Python als ich. unglücklich

Testscript

code:
1:
2:
3:
    for n in range(2,20):
        primes = eratosthenes(n)
        print(n, primes)
ergibt bei mir Ausgabe

2 [2]
3 [2, 3]
4 [2, 3]
5 [2, 3, 5]
6 [2, 3, 5]
7 [2, 3, 5, 7]
8 [2, 3, 5, 7]
9 [2, 3, 5, 7]
10 [2, 3, 5, 7]
11 [2, 3, 5, 7, 11]
12 [2, 3, 5, 7, 11]
13 [2, 3, 5, 7, 11, 13]
14 [2, 3, 5, 7, 11, 13]
15 [2, 3, 5, 7, 11, 13]
16 [2, 3, 5, 7, 11, 13]
17 [2, 3, 5, 7, 11, 13, 17]
18 [2, 3, 5, 7, 11, 13, 17]
19 [2, 3, 5, 7, 11, 13, 17, 19]

also zumindest bis dahin ist alles in Ordnung. Für n<2 ist es nicht geeignet, das zumindest ist richtig.
RavenOnJ Auf diesen Beitrag antworten »

My bad. geschockt Falsche Indentierung. unglücklich
HAL 9000 Auf diesen Beitrag antworten »

Wenn das Skript nicht gerade wegen eines Fehlers abbricht (davon hast du nicht gesprochen), muss ja die Ergebnisliste der letzten Zeile wegen mindestens die 2 umfassen, kann daher nicht leer sein. Von daher verstehe ich nicht im geringsten, wie da ein "None" zustande kommen soll, denn vorher gibt es keine return-Anweisung. unglücklich


P.S.: Die Python-Implementierungen, die ich kenne, verhalten sich relativ eklig, wenn man nicht die richtige Anzahl Leerzeichen bei den Einrückungen hat bzw. wenn irgendwelche Editoren da Leerzeichen in Tabulatoren umwandeln - vielleicht liegt da der Hase im Pfeffer.
HAL 9000 Auf diesen Beitrag antworten »

n=8 bzw. dann n1=4 ist der größte Wert, für den meine Hauptschleife "while (q1 < n1)" gar nicht durchlaufen wird, d.h., sofort abbricht, und danach kommt unmittelbar die return-Anweisung. Ist an sich kein Problem; für dein Python (aus mir nicht ersichtlichen Gründen) anscheinend aber doch.
RavenOnJ Auf diesen Beitrag antworten »

Siehe mein letztes Posting. Hatte falsch indentiert. unglücklich

PS: Genau da lag der Hase im Pfeffer. Mischung von Tabs und Spaces, bei der Bereinigung ist mir dann der Fehler bei der Indentierung unterlaufen. Ich weiß schon, warum ich C++ mag mit { und } und ;. (Natürlich nicht nur deswegen)
HAL 9000 Auf diesen Beitrag antworten »

Ja, bei diesen Einrückungen hab ich auch schon geflucht. Aber Python ist eben praktisch, wenn man mal schnell was zusammenklimpern will bzw. muss.

Sobald es aber auf Performance ankommt, und man sich nicht nur auf optimierte Bibliotheken beschränken kann, d.h. eigener Schleifencode (so wie oben) zum Tragen kommt, dann wird es lahm - ist halt bei einer Interpretersprache so.
ichwarneu Auf diesen Beitrag antworten »

Hallo ihr beiden und natürlich alle Mitleser Augenzwinkern

ich habe mich in Python etwas in List Comprehension eingearbeitet und würde euch gerne mal meinen Code zeigen. Es betrifft wieder das Sieb des Eratosthenes. Ich erzeuge eine Liste aller Zahlen von 2 bis zur Eingabe n. Dann nehme ich jeweils das erste nicht-gestrichene Element der Liste und streiche alle Vielfachen davon.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
import math

def eratosthenes(n):
    primes = [*range(2,n+1,1)]
    i = 0
    while i < math.floor(math.sqrt(n)):
        element = primes[i]
        primes = [x for x in primes if (x == element or x % element != 0)]
        i = i + 1
    return primes


Mir scheint es hier etwas umständlich, immer wieder von vorne bis zum ersten nicht-gestrichenen Element zu laufen. Wie kann ich dem Code sagen "Warte an der 2, streiche alle Vielfachen. Dann gehe eins weiter, streiche alle Vielfachen. Dann gehe eins weiter..." ?
ichwarneu Auf diesen Beitrag antworten »

Ich kann den Beitrag leider nicht mehr editieren. Hier eine etwas schnellere Version, aber nach wie vor der gleichen "Problematik" wie oben.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
import math

def eratosthenes(n):
    primes = [*range(3,n+1,2)]
    primes.insert(0, 2)
    i = 0
    element = 0
    while element <= math.floor(math.sqrt(n)):
        element = primes[i]
        primes = [x for x in primes if (x == element or x % element != 0)]
        i = i + 1
    return primes
HAL 9000 Auf diesen Beitrag antworten »

"Schnell" ist relativ. Ich hab das mal für auf meinem knapp 6 Jahre alten i7-4790K-PC ausgemessen: 48.4s

Zum Vergleich:

Variante RavenOnJ: 2.41s
Variante HAL 9000: 1.57s
ichwarneu Auf diesen Beitrag antworten »

Hallo HAL 9000,

das sind ja wirklich gravierende Unterschiede.
Mit Python mache ich mich ganz langsam vertraut. In deinem Code ist für mich sehr viel unbekanntes, aber ich wollte den Thread auch nicht dafür missbrauchen. Daher dachte ich, schreibe ich eine Routine, die ja "simpler" fast gar nicht sein kann. Aber das ist dann wohl das Thema Komplexität.
HAL 9000 Auf diesen Beitrag antworten »

Das Problem mit deinem Code ist, dass du für jede neu gefundene Primzahl die Liste komplett neu aufbaust. Im Fall betrifft das immerhin 446 Primzahlen, schon allein das erzeugt einen immensen Overhead.
ichwarneu Auf diesen Beitrag antworten »

Guten Morgen,

danke sehr, dann werde ich mich einfach mal sehr genau mit euren Codes auseinandersetzen.

Danke smile
HAL 9000 Auf diesen Beitrag antworten »

Wieviel schneller der Code von mir oben übrigens mit optimierten C++-Code geht:

: 0.017s
: 0.40s
: 4.6s

Natürlich ohne Bildschirmausgabe. Augenzwinkern
ichwarneu Auf diesen Beitrag antworten »

Aber wo wir gerade dabei sind HAL 9000, wie würde ich bei meinem letztgenannten Code die Komplexität bestimmen?

Die Eingabe ist und ich iteriere höchstens mal. Sei die in der Iterationen gewählte Zahl. Jedesmal streiche ich ja Zahlen.

Hm... fällt mir gerade wirklich sehr schwer diesen Zusammenhang zu sehen verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von ichwarneu
ich iteriere höchstens mal. Sei die in der Iterationen gewählte Zahl. Jedesmal streiche ich ja Zahlen.

Naja, das würde grob nach oben abgeschätzt Komplexität bedeuten.

Tatsächlich ist es weniger, aber dazu braucht man ein paar zahlentheoretische Kenntnisse zur Primzahlfunktion (= Anzahl Primzahlen ): Für die weiß man nämlich für große .

Im vorliegenden Fall streichst du nämlich nur die Vielfachen von Zahlen, genauer ist die Anzahl der Streichungen .
ichwarneu Auf diesen Beitrag antworten »

Danke sehr! Das ist wirklich sehr interessant, zumal ich zu "schüchtern" war zu sagen, dass ich dazu vielleicht den Primzahlsatz bräuchte Hammer

Der von dir genannte Code ist nicht nur viel schneller, sondern hat auch bessere Komplexität nehme ich an?
HAL 9000 Auf diesen Beitrag antworten »

Nein, das denke ich eher nicht: Die Komplexität wird dieselbe sein.

Die Komplexität gibt ja nicht die absolute Geschwindigkeit an, sondern nur die relative, d.h., wenn man etwa verdoppelt oder verzehnfacht für ein- und dieselbe Implementierung.


Z.B. der "Trick" nur die ungeraden Zahlen im Feld flag zu halten, bringt überhaupt keinen Gewinn an Komplexität - ja selbst auf Rechenzeit bezogen kaum einen, da er nur die Schleife mit einspart. Allerdings wird nur die Hälfte an Speicherplatz für "flag" benötigt, was zumindest bei und höher dann langsam eine Rolle spielen könnte. Augenzwinkern
ichwarneu Auf diesen Beitrag antworten »

Das Thema Komplexität ist für mich immer noch so schwer zu packen. Vielleicht sollte ich genau deshalb mal Komplexitätstheorie hören! Aber hier habe ich wieder jede Menge gelernt, danke dafür! smile
RavenOnJ Auf diesen Beitrag antworten »

@HAL9000

Weißt du, warum dein Code fast doppelt so schnell ist wie meiner? Ich sehe nicht, woran das liegt, habe aber deinen Code nicht so genau analysiert. verwirrt

Hast du dabei meine alte Version benutzt oder die derzeitige?

Edit: habe gerade noch die "harmlose" Zeile
code:
1:
2:
 
	lim = int((math.sqrt(n+1)-3)/2)+1

eingefügt als die obere Grenze des äußeren Loops. Dürfte etwas Laufzeit sparen. smile Bei läuft die äußere Schleife jetzt bis etwa , während sie vorher bis gelaufen ist. geschockt Das dürfte der Grund für die erheblich längere Laufzeit gewesen sein.

Auf meinem 3 Jahre alten Samsung S7: Pydroid3, Python 3.8
n = 10^7
HAL9000: 5,1 s
RavenOnJ: 6,1 s
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »