Unvollständige Probedivision

20.09.2021, 12:32

Malcang

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 $\begin{eqnarray*} n \end{eqnarray*}$ keinen Teiler $\begin{eqnarray*} p\leq\lfloor\sqrt{n}\rfloor \end{eqnarray*}$ , so ist sie prim.
Ich prüfe also alle Primzahlen bis zu dieser Grenze. Ist die Primzahl ein Teiler, so bilde ich $\begin{eqnarray*} n = \frac{n}{p} \end{eqnarray*}$ und prüfe mit dem so entstandenen Restfaktoren $\begin{eqnarray*} n \end{eqnarray*}$ weiter.
Liegt schlussendlich $\begin{eqnarray*} n=1 \end{eqnarray*}$ vor, so ist die Faktorisierung abgeschlossen.
Gilt $\begin{eqnarray*} p^2 > n \end{eqnarray*}$ , so ist der nun vorliegende Rest $\begin{eqnarray*} n \end{eqnarray*}$ prim.
Gebe ich nun eine niedrigere Obergrenze vor, so kann ich im Allgemeinen nicht mehr entscheiden, ob der "letzte Restfaktor $\begin{eqnarray*} n \end{eqnarray*}$ " 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 $\begin{eqnarray*} n=97 \end{eqnarray*}$ . Dann muss ich die Primzahlen $\begin{eqnarray*} 2,3,5,7 \end{eqnarray*}$ prüfen.
Diese teilen 97 jeweils nicht, also muss 97 eine Primzahl sein.
Ohne dieses Wissen gebe ich nun $\begin{eqnarray*} 97^{\frac{10}{21}} \end{eqnarray*}$ als Obergrenze vor. So erhalte ich ebenfalls die gleichen, zu prüfenden Primzahlen.
Nun ist $\begin{eqnarray*} 7^2 < 97 \end{eqnarray*}$ , 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 $\begin{eqnarray*} 97^{\frac{1}{2}} \end{eqnarray*}$ die gleichen Primzahlen gefunden hätte.

Ich habe das mal algorithmisch aufgeschrieben:
[attach]53675[/attach]
Dieser Algo liefert mir bei Eingabe 97 mit Obergrenze $\begin{eqnarray*} \sqrt{97} \end{eqnarray*}$ trotzdem die Aussage, dass 97 eventuell nicht prim ist.

Da frage ich mich: Kann ich mit einer anderen Obergrenze die Primalität überhaupt entscheiden?

20.09.2021, 12:57

HAL 9000

Auf diesen Beitrag antworten »

RE: Unvollständige Probedivision

Zitat:

Original von ichwarneu
Ohne dieses Wissen gebe ich nun $\begin{eqnarray*} 97^{\frac{10}{21}} \end{eqnarray*}$ als Obergrenze vor.

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

Erstaunt1

Zitat:

Original von ichwarneu
Nun ist $\begin{eqnarray*} 7^2 < 97 \end{eqnarray*}$ , also müsste ich an dieser Stelle ja sagen dass ich nicht weiß, ob 97 prim ist

Es geht nicht darum, dass $\begin{eqnarray*} 7^2 < 97 \end{eqnarray*}$ ist, sondern dass für die nächste Primzahl dann $\begin{eqnarray*} 11^2 > 97 \end{eqnarray*}$ 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.

20.09.2021, 13:07

Malcang

Auf diesen Beitrag antworten »

RE: Unvollständige Probedivision

Zitat:

Original von HAL 9000

Zitat:

Original von ichwarneu
Ohne dieses Wissen gebe ich nun $\begin{eqnarray*} 97^{\frac{10}{21}} \end{eqnarray*}$ als Obergrenze vor.

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

Erstaunt1

Ich wollte eine Grenze haben, die so beschaffen ist, dass sie mir die gleichen Primzahlen ausgibt wie bei $\begin{eqnarray*} 97^{\frac{1}{2}} \end{eqnarray*}$ als Obergrenze. Mit der dritten Wurzel wäre das schon nicht mehr gelungen.

Zitat:

Original von HAL 9000
Es geht nicht darum, dass $\begin{eqnarray*} 7^2 < 97 \end{eqnarray*}$ ist, sondern dass für die nächste Primzahl dann $\begin{eqnarray*} 11^2 > 97 \end{eqnarray*}$ 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 $\begin{eqnarray*} p^2 > n \end{eqnarray*}$ 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 $\begin{eqnarray*} 7^2 < 97 \end{eqnarray*}$ ist, sondern dass für die nächste Primzahl dann $\begin{eqnarray*} 11^2 > 97 \end{eqnarray*}$ 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.

20.09.2021, 13:08

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.

20.09.2021, 13:13

Malcang

Auf diesen Beitrag antworten »

HAL, jetzt hast du im gleichen Moment eine Antwort geliefert, in der ich meine editiert habe Big Laugh

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.

20.09.2021, 13:16

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.

Anzeige

20.09.2021, 13:24

Malcang

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 $\begin{eqnarray*} n = 146.955 \end{eqnarray*}$ .
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" ?

20.09.2021, 13:26

HAL 9000

Auf diesen Beitrag antworten »

Das $\begin{eqnarray*} g \end{eqnarray*}$ 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 $\begin{eqnarray*} \sqrt[g]{n} \end{eqnarray*}$ statt $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ steht. (Zumal in deinem Erklärtext nirgendwo auch nur dieses $\begin{eqnarray*} g \end{eqnarray*}$ erwähnt wurde.) Augenzwinkern

Augenzwinkern

Im Fall $\begin{eqnarray*} g=2 \end{eqnarray*}$ ist jedenfalls klar, dass die Primfaktorzerlegung vollständig ist und damit nichts fehlt.

Für $\begin{eqnarray*} g>2 \end{eqnarray*}$ kann das mit dem FALSE Sinn machen: Das deutet dann an, dass der letzte Eintrag vorher nicht notwendig eine Primzahl ist.

20.09.2021, 13:31

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Das $\begin{eqnarray*} g \end{eqnarray*}$ 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 $\begin{eqnarray*} \sqrt[g]{n} \end{eqnarray*}$ statt $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ steht. Augenzwinkern

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 $\begin{eqnarray*} g>2 \end{eqnarray*}$ wirklich eindeutig angeben kann.

20.09.2021, 13:40

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Für $\begin{eqnarray*} g>2 \end{eqnarray*}$ 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 $\begin{eqnarray*} g>2 \end{eqnarray*}$ setze, falls nicht $\begin{eqnarray*} n == 1 \end{eqnarray*}$ auftreten sollte.
Ich fand das bisher etwas unbefriedigend. Aber dein erster Hinweis $\begin{eqnarray*} 11^2 > 97 \end{eqnarray*}$ passt dahingehend vielleicht doch, denn bei $\begin{eqnarray*} g = 2 \end{eqnarray*}$ weiß ich, dass alle Primzahlen die überhaupt infrage kommen (gesiebt mit Eratosthenes) vorliegen.
Meine Vermutung ist, dass ich das im Falle $\begin{eqnarray*} g>2 \end{eqnarray*}$ nicht mehr entscheiden kann und mir das einen Strich durch die Rechnung macht.

20.09.2021, 13:59

Malcang

Auf diesen Beitrag antworten »

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

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

20.09.2021, 14:32

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.

20.09.2021, 17:38

Malcang

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

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

21.09.2021, 13:49

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 $\begin{eqnarray*} O\left(n\log(n)\right) \end{eqnarray*}$ ) 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 $\begin{eqnarray*} O(n) \end{eqnarray*}$ 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]

21.09.2021, 16:29

Malcang

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

smile

21.09.2021, 16:47

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 $\begin{eqnarray*} i \end{eqnarray*}$ , sondern die ungerade Zahl $\begin{eqnarray*} 2i+1 \end{eqnarray*}$ , d.h., die geraden Zahlen lasse ich von vornherein außen vor. Außerdem beginne ich pro Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ erst mit dem Streichen der Zahl $\begin{eqnarray*} q=p^2 \end{eqnarray*}$ , dann $\begin{eqnarray*} p(p+2) \end{eqnarray*}$ , $\begin{eqnarray*} p(p+4) \end{eqnarray*}$ usw. - das reicht, da alle kleineren Vielfachen von $\begin{eqnarray*} p \end{eqnarray*}$ eh schon vorher gestrichen wurden.

21.09.2021, 16:53

Malcang

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

Augenzwinkern

21.09.2021, 17:40

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

smile

21.09.2021, 17:52

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

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.

21.09.2021, 18:08

RavenOnJ

Auf diesen Beitrag antworten »

My bad.

geschockt

Falsche Indentierung. unglücklich

unglücklich

21.09.2021, 18:11

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

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.

21.09.2021, 18:39

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.

21.09.2021, 18:47

RavenOnJ

Auf diesen Beitrag antworten »

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

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)

22.09.2021, 08:57

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.

23.09.2021, 21:30

Malcang

Auf diesen Beitrag antworten »

Hallo ihr beiden und natürlich alle Mitleser Augenzwinkern

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..." ?

23.09.2021, 21:58

Malcang

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

23.09.2021, 23:02

HAL 9000

Auf diesen Beitrag antworten »

"Schnell" ist relativ. Ich hab das mal für $\begin{eqnarray*} n=10^7 \end{eqnarray*}$ auf meinem knapp 6 Jahre alten i7-4790K-PC ausgemessen: 48.4s

Zum Vergleich:

Variante RavenOnJ: 2.41s
Variante HAL 9000: 1.57s

23.09.2021, 23:16

Malcang

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.

24.09.2021, 10:16

HAL 9000

Auf diesen Beitrag antworten »

Das Problem mit deinem Code ist, dass du für jede neu gefundene Primzahl $\begin{eqnarray*} \mbox{element} < \sqrt{n} \end{eqnarray*}$ die Liste komplett neu aufbaust. Im Fall $\begin{eqnarray*} n=10^7 \end{eqnarray*}$ betrifft das immerhin 446 Primzahlen, schon allein das erzeugt einen immensen Overhead.

24.09.2021, 11:09

Malcang

Auf diesen Beitrag antworten »

Guten Morgen,

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

Danke smile

smile

24.09.2021, 11:45

HAL 9000

Auf diesen Beitrag antworten »

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

$\begin{eqnarray*} n=10^7 \end{eqnarray*}$ : 0.017s
$\begin{eqnarray*} n=10^8 \end{eqnarray*}$ : 0.40s
$\begin{eqnarray*} n=10^9 \end{eqnarray*}$ : 4.6s

Natürlich ohne Bildschirmausgabe. Augenzwinkern

Augenzwinkern

24.09.2021, 12:59

Malcang

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 $\begin{eqnarray*} n \end{eqnarray*}$ und ich iteriere höchstens $\begin{eqnarray*} \sqrt{n}-1 \end{eqnarray*}$ mal. Sei $\begin{eqnarray*} p \end{eqnarray*}$ die in der Iterationen gewählte Zahl. Jedesmal streiche ich ja $\begin{eqnarray*} \frac{n}{p} \end{eqnarray*}$ Zahlen.

Hm... fällt mir gerade wirklich sehr schwer diesen Zusammenhang zu sehen verwirrt

verwirrt

24.09.2021, 13:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichwarneu
ich iteriere höchstens $\begin{eqnarray*} \sqrt{n}-1 \end{eqnarray*}$ mal. Sei $\begin{eqnarray*} p \end{eqnarray*}$ die in der Iterationen gewählte Zahl. Jedesmal streiche ich ja $\begin{eqnarray*} \frac{n}{p} \end{eqnarray*}$ Zahlen.

Naja, das würde grob nach oben abgeschätzt Komplexität $\begin{eqnarray*} O(n\sqrt{n)} \end{eqnarray*}$ bedeuten.

Tatsächlich ist es weniger, aber dazu braucht man ein paar zahlentheoretische Kenntnisse zur Primzahlfunktion $\begin{eqnarray*} \pi(x) \end{eqnarray*}$ (= Anzahl Primzahlen $\begin{eqnarray*} \leq x \end{eqnarray*}$ ): Für die weiß man nämlich $\begin{eqnarray*} \pi(x)\sim \frac{x}{\ln(x)} \end{eqnarray*}$ für große $\begin{eqnarray*} x \end{eqnarray*}$ .

Im vorliegenden Fall streichst du nämlich nur die Vielfachen von $\begin{eqnarray*} \pi(\sqrt{n}) \end{eqnarray*}$ Zahlen, genauer ist die Anzahl der Streichungen $\begin{eqnarray*} \sum_{k=1}^{\pi(\sqrt{n})} \frac{n}{p_k}\approx n\int\limits_2^{\sqrt{n}}\frac{\dd x}{x\ln(x)} \approx n\ln\left(\ln(\sqrt{n})\right) \end{eqnarray*}$ .

24.09.2021, 13:29

Malcang

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

Hammer

Der von dir genannte Code ist nicht nur viel schneller, sondern hat auch bessere Komplexität nehme ich an?

24.09.2021, 13:33

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 $\begin{eqnarray*} n \end{eqnarray*}$ 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 $\begin{eqnarray*} p=2 \end{eqnarray*}$ einspart. Allerdings wird nur die Hälfte an Speicherplatz für "flag" benötigt, was zumindest bei $\begin{eqnarray*} n=10^9 \end{eqnarray*}$ und höher dann langsam eine Rolle spielen könnte. Augenzwinkern

Augenzwinkern

24.09.2021, 13:39

Malcang

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

smile

25.09.2021, 16:47

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

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

smile

Bei $\begin{eqnarray*} n=10^7 \end{eqnarray*}$ läuft die äußere Schleife jetzt bis etwa $\begin{eqnarray*} \frac 1 2\sqrt{10^7}\simeq 1,6*10^3 \end{eqnarray*}$ , während sie vorher bis $\begin{eqnarray*} 10^7/4= 2,5*10^6 \end{eqnarray*}$ gelaufen ist. geschockt

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

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »