Primzahlen berechnen mit nur wenigen Befehlen

[niggeden]

Hi!

Wir sollten uns mal Gedanken darüber machen, wie man mit Delphi 6 ein Programm schreiben kann, das Primzahlen "entlarvt".
In der Konsolenanwendung am Ende soll dann z.b. stehen:
Zahl 10 keine Primzahl
Zahl 11 Primzahl
usw.


Da wir aber kaum Befehle kennen können wir das meiner Meinung nach nur mit Divisionen erreichen.

Wir würdet ihr das machen?

MfG

[Klaus01]

Hallo,

gebe mal im Suchfeld "isPrim" an, Du wirst dann einige Treffer mit Beispielen erhalten.

Grüße
Klaus

[3_of_8]

Tipp: Eine Zahl n ist eine Primzahl, wenn sie durch keine natürliche Zahl von 2 bis Wurzel(n) teilbar ist. (Ausnahme: Die 1 ist auch keine)

[jfheins]

Möchtest du

1. Einen Test, der prüft, ob eine bestimt Zahl prim ist oder

2. Ein Verfahren, das für einen bestimmten Bereich alle Primzahlen heraussucht?

Das sind 2 verschiedene Dinge, und das eine zu verwenden um das andere zu erreichen ist eher ... unperformant ;)

zu 1. wie Manuel vorgeschlagen hat, musst du alle potenziellen Teiler-Kanidaten prüfen.

zu 2. Da gibt es das Sieb des Eratosthenes, ist auf Wikipedia relativ gut erklärt. Damit sparst du Aufwand, wenn du sowiso alle Zahlen von 1 bis n auf "Primheit" untersuchen möchtest.

[Apollonius]

Dann gibt es natürlich noch die probabilistischen Primzahltests. Dort können als prim angegebene Zahlen noch mit einer geringen Wahrscheinlichkeit zusammengesetzt sein. Dafür sind diese Tests extrem schnell. Die Fehlerwahrscheinlichkeit kann man ziemlich stark verringern, indem man die Iterationszahl vergrößert. Beispielsweise ist beim Miller-Rabin-Test die Wahrscheinlichkeit, dass eine nicht-Primzahl als prim angegeben wird, bei zwanzig Iterationen geringer als ein Billionstel.

[chamop87]

Zitat:

Tipp: Eine Zahl n ist eine Primzahl, wenn sie durch keine natürliche Zahl von 2 bis Wurzel(n) teilbar ist. (Ausnahme: Die 1 ist auch keine)

zwei ist auch eine primzahl, weil sie nur durch 2 und 1 teilbar ist!

[STS301]

schau dir das einmal an
http://www.delphipraxis.net/internal...922&highlight=

[3_of_8]

Zitat:

Zitat von chamop87

Zitat:

Tipp: Eine Zahl n ist eine Primzahl, wenn sie durch keine natürliche Zahl von 2 bis Wurzel(n) teilbar ist. (Ausnahme: Die 1 ist auch keine)

zwei ist auch eine primzahl, weil sie nur durch 2 und 1 teilbar ist!

Und? Für n:=2 ist aber deine rechte Intervallgrenze (sqrt(2)) kleiner als die linke Intervallgrenze (2), sodass du überhaupt keine Zahl überprüfst, wenn du den von mir vorgeschlagenen Algorithmus anwendest.

[jokerfacehro]

den einfachsten primzahl algorithmus den ich gesehn hab, war nur mit addition und sehr einfach.

siehe hier, is glaub ich der 2. oder 3 beitrag http://www.delphipraxis.net/internal...ct.php?t=40427