C++ Programm Primzahlen?
Hallo Zusammen,
ich lerne zurzeit die Programmierung in C und C++ für meine Studium.
Ich soll ein Programm entwickeln das die Primzahlen bis 100 ausgibt.
Dazu habe ich folgende Musterlösung. Allerdings verstehe ich noch nicht zu 100% was das Programm genau bewirkt. Erklärung vom Professor fehlen leider komplett.
Ich kennen das Prinzip der Anwendung von Arrays
Allerdings erschließt sich mir die Vorgehensweise des Programm nicht.
Gibt es jemanden der mir Zeile für Zeile erläutern kann was die einzelnen Programmzeilen für Berechnungen durchführen bzw bewirken?
Ich verlieren als kompletter Neuling doch noch sehr schnell die Übersicht, selbst wenn ich auf dem Papier die einzelnen Zeilen versuche nach zurechnen.
Soviel hab ich verstanden das der Index des Arrays mit 1 zugewiesen wird, wenn eine Primzahl vorliegt, ansonsten wird das Feld mit 0 beschrieben.
Vielen Dank für eure Hilfe
#include <stdio.h>
#define N 100
int main()
{
int i, j, a[N+1];
a[1] = 0;
for (i = 2; i <= N; i++) a[i] = 1;
for (i = 1; i <= N; i++)
if (a[i]) printf("%d", i);
for (i = 2; i <= N / 2; i++)
for (j = 2; j <= N/i; j++)
a[i * j] = 0;
printf("\n Berechn. der Primzahlen < 100: \n");
for (i = 1; i <= N; i++)
if (a[i]) printf("\n %d", i);
printf("\n Ende des Programms \n");
return 0;
}
2 Antworten
C++ ist leider nicht meine Disziplin aber ich versuchs mal:
#include <stdio.h> // Standard Input Output
#define N 100 // Konstante N=100
int main() // ohne Worte
{
int i, j, a[N+1]; // Deklaration der Variablen
a[1] = 0; // 1=0 denn die erste Primzahl ist 2
for (i = 2; i <= N; i++) a[i] = 1; // Alle auf 1
for (i = 1; i <= N; i++) // Durchlauf
if (a[i]) printf("%d", i); // Falls a[i] gib i aus (verstehe ich nicht)
for (i = 2; i <= N / 2; i++) // Durchlauf 1. Instanz
for (j = 2; j <= N/i; j++) // Durchlauf verschachtelt
a[i * j] = 0; // alle Felder in a[] die keine Primzahl sind als sich restlos dividieren lassen auf 0
printf("\n Berechn. der Primzahlen < 100: \n"); // Text ausgabe
for (i = 1; i <= N; i++) // Durchlauf
if (a[i]) printf("\n %d", i); Falls a[i] ungleich 0 ist i eine Primzahl und wird ausgegeben
printf("\n Ende des Programms \n"); // Ohne Worte
return 0; // Tschüss
Vielen Dank. Mit dem Ansatz deines Vorposter + deine Erläuterung helfen mir bestimmt weiter
Das ist ein Eratosthenes-Sieb. Das ist hier ganz gut erklärt - versuch erstmal den Algorithmus als Ganzes zu verstehen, bevor du dich an den Code selbst wagst. Vereinfacht gesagt wird hier anfangs davon ausgegangen, dass alle Zahlen im Array, die größer als 1 sind, eine Primzahl sind. Und dann werden alle Quadratzahlen (also 2*2, 2*3, 2*4, ... die Variablen i und j bei dir im Code) gestrichen. Was danach noch übrig bleibt, ist eine Primzahl.
Fast, nicht Quadratzahlen werden gestrichen, sondern alle ganzzahligen Vielfachen - Nach der Aussage mit der Quadrahzahl hast Du es exemplarisch richtig hingeschrieben).
Danke für den Hinweis. Das ist aufjedenfall ein guter Ansatzpunkt der mir bestimmt weiterhilft.
Allgemein: probier solche Sachen aus. Wenn du i hier von 2 bis N laufen lässt, also
for (i = 2; i <= N; i++) {
, dann stürzt dein Programm ab, weil in
a[i * j] = 0;
irgendwann die Größe des Arrays überschreiten wird. Das müsstest du dann also vorher abfangen.
Mathematisch ganz richtig ist der Teil nicht, es würde reichen, wenn du i von 2 bis zur Wurzel (und nicht bis zur Hälfte) von N laufen lassen würdest. Das ist in dem verlinkten Skript auf Seite 4 so erklärt, warum es über der Wurzel keine Ergebnisse geben kann.
Neben der Sache mit den Abstürzen (die man durch eine einfache if-Bedingung abfangen könnte) macht man das also, damit der Algorithmus schneller durchläuft.
Ist dies zur Verringerung der Berechnungszeit ?
Nicht wirklich. Schau dir mal die innere Schleife für den letzten Wert i==N/2 an (angenommen, N ist gerade). Wegen N/i=N/(N/2)=2 steht da effektiv:
for (j = 2; j <= 2; j++)
das heißt, die Schleife läuft genau einmal durch. Für jedes größere i läuft j von 2 bis 1, wird also nicht mehr ausgeführt. Deshalb ist es unnötig (aber nicht falsch), die äußere Schleife weiter als N/2 gehen zu lassen.
Gilt das auch bei ungeradem N? Reicht hier i=(N-1)/2 als letzter Wert oder muss man vielleicht doch manchmal den nächsten Wert i=(N+1)/2 mitnehmen? Die meisten Programmierer werden dieses Problem entweder übersehen oder an einem Beispiel verifizieren, z.B. für N=9:
- i=2...9/2=4 ⇒ j=2...9/4=2 — noch ein Durchlauf.
- i=2...4+1=5 ⇒ j=2...9/5=1 — kein Durchlauf mehr.
Sieht also gut aus. Aber wenn der Code in einem Herzschrittmacher oder einer Raketensteuerung läuft, muss ein mathematischer Beweis dafür her, dass N/2 in der äußeren Schleife wirklich immer als Obergrenze ausreicht.
dann stürzt dein Programm ab, weil in
a[i * j] = 0;
irgendwann die Größe des Arrays überschreiten wird
Nein. Die innere Schleife geht nur bis j=N/i. Also ist j*i≤(N/i)*i≤N. Das Array a ist N+1 lang, also passt a[i*j] immer.
Der Algorithmus ist mir nun soweit klar geworden. Das hat die Sache deutlich vereinfacht. Eine Weiter frage hätte ich noch.
<<<<<for (i = 2; i <= N / 2; i++)<<<<<<
for (j = 2; j <= N/i; j++)
a[i * j] = 0;
der teil des Programms zwischen den Pfeilen, wozu dient der? Nach meinem Verständnis sollte das Programm auch ohne diesen Teil ablauffähig sein und die korrekten Zahlen liefern.. Ist dies zur Verringerung der Berechnungszeit ?
Vielen Dank