Primzahlen

[problembär]

Hallo,

Primzahlen berechnen, ist ja ein beliebtes Programmierthema bei Lehrern.
Ich mußte das nie machen und hab' mir auch nicht viele Lösungen angesehen.
Vielleicht ging mir gerade deshalb manchmal diese Idee im Kopf rum. Also:
Wenn man ohne Rechner wissen will, ob eine Zahl eine Primzahl ist, prüft man wohl zuerst, ob sie durch 2 oder durch 3 teilbar ist.
Wenn das nicht der Fall ist, kann es aber noch größere Teiler geben.
Mein Gedanke, den bestimmt schon viele andere hatten, war, daß auch diese Teiler nicht beliebig groß sein können. Mit jeder Prüfung verringert sich sogar ihre mögliche Größe. Beispiel:

1. Prüfung: 17 ist nicht durch 2 teilbar. 9 * 2 wären schon 18. Die Teiler, die man noch prüfen müßte, müßten also kleiner als 9 sein.
2. Prüfung: 17 ist nicht durch 3 teilbar. 6 * 3 wären schon 18. Die Teiler, die man noch prüfen müßte, müßten also kleiner als 6 sein.
Usw.

Wenn man ein Primzahl prüft, erreicht die mögliche Größe der Teiler irgendwann die schon geprüften Teiler. Dann braucht man nicht mehr weiter zu prüfen (und weiß, daß es eine Primzahl ist).

Hab' das grad' mal versucht, in Code umzusetzen:

Code: Alles auswählen

#!/usr/bin/env python
# coding: iso-8859-1

def isPrim(num):
    """ Not sure, if this works correctly. """
    uplim = num
    count = 2.
    while count < uplim:
        if not (num % count):
            return False
        uplim = num // count + 1
        count += 1.
    return True

for i in range(3, 201, 1):
    if isPrim(float(i)):
        print i

Ich war recht überrascht, daß das aus dem Stand zu funktionieren schien.
So, jetzt ist es ausnahmsweise mal willkommen, wenn ihr gründlich darüber ablästert. Ist das vielleicht der gängige Ansatz (Rad nochmal erfunden)? Oder ist das falsch, d.h. es funktioniert irgendwann nicht oder man kann es noch viel besser schreiben?

Viel Spaß

[EyDu]

Unglaublich, dann kann man ja bei sqrt(num) aufhören! Ok, eigentlich ist daran nichts unglaublich, da das wahrscheinlich seit Jahrhunderten bereits bekannt und die übliche Standardoptimierung in solch einfachen Umsetzungen ist. Noch schneller wird es übrigens, wenn du nur gegen ungerade Zahlen testest.

Edit: was genau soll das `float` dort bezwecken?

[problembär]

Ah, die übliche Standardoptimierung. Gut, dann weiß ich das jetzt. Danke.

was genau soll das `float` dort bezwecken?

Na ja, es ist ja immer ein Problem, Divisionen mit Integern durchzuführen, weil die Nachkommastelle ggf. abgeschnitten wird.

Code: Alles auswählen

>>> print 5 / 2
2

Die Rechenfehler sind dann auch schwer zu finden, weil es ja keine Fehlermeldung gibt.
Deshalb versuche ich normalerweise schon im Code sicherzustellen, daß alle Zahlen, mit denen ich Divisionen ausführen möchte, deutlich als float gekennzeichnet sind.

[naeg]

Der/einer der Besten Algorithmen zur Berechnung von Primzahlen, ist das Sieb von Atkin:

Code: Alles auswählen

from math import sqrt

def sieve_of_atkin(limit):
    results = [2, 3, 5]
    sieve = [False] * (limit + 1)
    factor = int(sqrt(limit)) + 1

    for i in range(1, factor):
        for j in range(1, factor):
            n = 4 * i**2 + j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3 * i**2 + j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3 * i**2 - j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
   
    for index in range(5, factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
   
    for index in range(7, limit):
        if sieve[index]:
            results.append(index)
   
    return results

Einfach

Code: Alles auswählen

sieve_of_atkin(1000000)

um die ersten Millionen Primzahlen zu erhalten.

[EyDu]

Dann solltest du die Umwandlung mittels float allerdings in der `isPrim`, welches `is_prime` heißen sollte, machen. `num` sollte auf jeden Fall eine Ganzzahl bleiben, da nur auf diesen ein Primzahltest sinn macht. `uplim` könnte dann mittels float umgesetzt werden.

Der Standardansatz sieht in etwa so aus:

Code: Alles auswählen

def is_prime(value):
    yield 2
    for i in range(3, int(value**0.5), 2):
        if not (value % i):
            yield i

[numerix]

Der/einer der Besten Algorithmen zur Berechnung von Primzahlen, ist das Sieb von Atkin:

So würde ich das nicht stehen lassen wollen. Das Sieb von Atkin ist ein effizientes Siebverfahren zur Berechnung einer großen Menge von aufeinanderfolgenden Primzahlen, und eben auch nur dann ein sinnvoller Algorithmus, wenn man so etwas will. Geht es hingegen darum, einzelne (speziell größere) Primzahlen auf Primalität zu prüfen, dann ist das der falsche Ansatz.
Als den "besten" Algorithmus würde ich ihn auch nicht bezeichnen. Zwar ist das Sieb von Atkin theoretisch schneller als das konzeptionell einfachere Sieb des Eratosthenes, praktisch aber nicht unbedingt.

Speziell was Python angeht, so lässt sich - zumindest nach meiner Erfahrung - das Sieb des Eratothenes effizienter implementieren als der Atkin, was vor allem daran liegt, dass beim Aktin viele zusätzliche Berechnungen erforderlich sind. Auch der Einsatz von psyco ändert grundsätzlich daran nichts.

Was die gezeigte Implementation angeht, so kann man mit der im übrigen keinen Blumentopf gewinnen. Eine (richtig) gute Implementation des Eratosthenes ist mehr als 20x schneller (und zwar sowohl mit als auch ohne psyco) ...

[problembär]

Hmm, "Sieb des Eratosthenes"? Na ja, will mich ja nicht mit Mathematikern vergleichen, auch nicht mit antiken.
Was mir in dem Beispiel allerdings nicht so gut gefällt, ist, daß offenbar erstmal alle zu prüfenden Zahlen in einer Liste gespeichert werden müssen. Bei so vielen Zahlen wird die Liste ja recht groß und verbraucht entsprechend Speicher.
Bei "meinem" Ansatz kommt man ohne nennenswerten Speicherverbrauch aus, der z.B. ja noch in den '80er Jahren, als man auch schon über Primzahlprogramme nachdachte, ein echtes Problem darstellte (z.B. ZX Spectrum: 40K RAM frei für Programme, beim C64 war's nicht viel besser, weil das Basic jeweils auch einiges schluckte).

Jedenfalls vielen Dank für die weiteren Hinweise.

Gruß

[BlackJack]

@problembär: Das Sieb ist ja auch nicht zum Testen einer Zahl da, sondern um *alle* Primzahlen in einem bestimmten Bereich zu ermitteln. Und da kommt man um Speicherverbrauch nicht herum, wenn man es nicht deutlich ineffizienter lösen möchte.

Mit 40 KiB kann man Bereiche aussieben, bei denen Spectrum & Co schon ziemlich lange dran knabbern müssen. Man muss ja nur speichern ob eine Zahl Prim ist oder nicht = 1 Bit, man kann also diese Information von jeweils 8 Zahlen in ein Byte quetschen. Ausserdem braucht man mit Ausnahme der 2 nur ungerade Zahlen betrachten. Das heisst man braucht nur ein Bit für jede zweite Zahl in dem Suchbereich speichern. 40 KiB reichen also für einen Bereich von mehr als eine halbe Million Zahlen aus. Da der Algorithmus quadratische Laufzeit hat, würde ich mir bei den Heimcomputern eher Gedanken um die Zeit und nicht um den Speicher machen.

Wenn man erst einmal Primzahlen ”gesiebt” hat, kann man die auf Band oder Diskette speichern und dann zum Testen anderer Zahlen verwenden.

[problembär]

Mit 40 KiB kann man Bereiche aussieben, bei denen Spectrum & Co schon ziemlich lange dran knabbern müssen. Man muss ja nur speichern ob eine Zahl Prim ist oder nicht = 1 Bit, man kann also diese Information von jeweils 8 Zahlen in ein Byte quetschen. Ausserdem braucht man mit Ausnahme der 2 nur ungerade Zahlen betrachten. Das heisst man braucht nur ein Bit für jede zweite Zahl in dem Suchbereich speichern. 40 KiB reichen also für einen Bereich von mehr als eine halbe Million Zahlen aus.

Ja, da hat man damals wohl viel mit Bits gearbeitet.
----
Hab' meinen Kram spaßeshalber auch noch mal nach C übertragen:

Code: Alles auswählen

#include <stdio.h>

/* myprim.c */

int is_prim(int num);

int main(void)
{
    int i;
    for (i = 3; i <= 200; i++) {
        if (is_prim(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

int is_prim(int num) {
    int uplim;
    int count;
    uplim = num;
    count = 2;
    while (count < uplim) {
        /* Modulo geht anscheinend nur mit Integern: */
        if (num % count) {
            /* Bei der Division mit Integern werden die Nachkommastellen abgeschnitten, was hier erwünscht ist: */
            uplim = num / count + 1;
            count ++;
        } else {
            return 0;
        }
    }
    return 1;
}

Gruß

[lunar]

@numerix: Als Anmerkung dazu: Im Haskell Wiki[/url] gibt es einen interessanten Artikel zur Primzahlberechnung mit einem Abschnitt über die effiziente Implementierung des Sieb des Eratothenes.

[numerix]

@lunar: Interessanter Artikel, leider zu lang und zu gehaltvoll für "mal eben durchlesen". Inwieweit er einen Ertrag für eine effiziente Python-Implementation abwirft, ist natürlich ein anderer Punkt.

[mkesper]

was genau soll das `float` dort bezwecken?

Na ja, es ist ja immer ein Problem, Divisionen mit Integern durchzuführen, weil die Nachkommastelle ggf. abgeschnitten wird.

Code: Alles auswählen

>>> print 5 / 2
2

Setze einfach

Code: Alles auswählen

from __future__ import division

an den Anfang des Quelltextes, dann ist dieses Fehlverhalten weg. Bei Python 3.x ist dieses zum Glück bereits Standard.

[BlackJack]

@problembär: Dein `is_prim()` in C hält 0 und 1 auch für prim.

[numerix]

@problembär: Dein `is_prim()` in C hält 0 und 1 auch für prim.

Seine Python-Fassung auch ...

[BlackJack]

Ich habe jetzt mal ein Programm in C geschrieben, dass 32KiB „aussiebt” und in diesem Speicherbereich die Information für jeweils acht ungerade Zahlen in einem Byte zusammen fasst. Man hat also am Ende eine Nachschlagetabelle für die ungeraden Zahlen von 1 bis 524.287. Ich war überrascht, dass es auf dem C64 nur etwas unter drei Minuten braucht diese Tabelle zu berechnen. Hätte gedacht es würde länger dauern.

[problembär]

@problembär: Dein `is_prim()` in C hält 0 und 1 auch für prim.

Seine Python-Fassung auch ...

Bin halt von mitdenkenden Menschen ausgegangen, die gar nicht erst versuchen, 0 und 1 auf Primzahlqualität zu überprüfen.
Man kann aber auch

Code: Alles auswählen

if (num < 2) {
    return 0;
}

einfügen. Is schwer, ne?

[lunar]

@problembär: Offenbar zu schwer für Dich selbst ...

[Lexi]

Code: Alles auswählen

def prime(a):
	NPlist = []
	for i in range(2, round(m.sqrt(a)+1)):
		if a%i == 0:
			NPlist += [a]
			break
	if a not in NPlist:
		print(a, "{prime}")

Dies ist mein Lösungsvorschlag.
So wird eine Liste erstellt, in der a vorhanden ist, wenn diese nicht prim ist. Sollte a also prim sein, ist dieses nicht in der NPlist.


LG
Lexi

[Lexi]

Code: Alles auswählen

 def prime(a):
	NPlist = []
	for i in range(2, round(m.sqrt(a)+1)):
		if a%i == 0:
			NPlist += [a]
			break
	if a not in NPlist:
		print(a, "{prime}")

[Jankie]

Code: Alles auswählen

 def prime(a):
	NPlist = []
	for i in range(2, round(m.sqrt(a)+1)):
		if a%i == 0:
			NPlist += [a]
			break
	if a not in NPlist:
		print(a, "{prime}")

Hey,

der Code mag zwar funktionieren (keine Fehlermeldung), gut lesbar ist er aber nicht. a, i und NPlist sind keine guten Variablennamen, da diese nichts sagend sind. Auch Datentypen wie "list" sollen eigentlich nicht in einem Variablenamen vorkommen, da sich das ja stets ändern kann. Laut PEP8 Style Guide wird alles in Python klein_mit_unterstrich geschrieben, außer Klassen (werden in MixedCase) und Konstaten (KOMPLETTGROSS). Einrücken sollte man mit 4 Leerzeichen und nicht mit Tabs.

Wenn ich die Funktion mit 25 aufrufe, bekomme ich folgendes als Ausgabe:

Code: Alles auswählen

25 {prime}
25 {prime}
25 {prime}

Also drei Mal eine Ausgabe, aber 25 ist keine Primzahl.