Moin ich habe erst vor kurzem angefangen mit dem Programmieren !
Ich habe folgendes Problem, ich habe hier einen Abschnitt von einem Code
bei dem ich nicht ganz verstehe was hier gemacht wird. Es wäre hilfreich
wenn jemand mir den Code erklären könnte oder eventuell diesen Code mit
Kommentaren beschmücken könnte.
Hier der Code:
for (i = 2; i <= eingabe; i++)
{
if (array[i] == 1)
{
int j = i * 2;
while (j <= eingabe)
{
array[j] = 0;
j = j + i;
}
}
}
printf ("\nDie Primzahlen lauten: \n");
for (int i = 2; i <= eingabe; i++)
{
if (array[i])
{
printf ("%d, ", i);
}
:
Verschoben durch Moderator
Taw U. schrieb: > Ich habe folgendes Problem, ich habe hier einen Abschnitt von einem Code > bei dem ich nicht ganz verstehe was hier gemacht wird. Fang doch in deinem Buch/Tutorial/"was auch immer" am Anfang an und nicht in der Mitte. Dann lernst du nämlich alle Codeteile nacheinander.
ist mir schon klar nur ich musste hierbei den abschnitt dieses codes erklären können
dummschwaetzer schrieb: > https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes Wie merkt man das anhand des codes, also womit wird das Sieb angewendet, bzw. was wird wo gemacht ?
Möglichkeit 1: Das sind Hausaufgaben. In diesem Fall lautet die Antwort: Es sind deine Hausaufgaben, du sollst sie machen. Nimm dir ein Blatt Papier, male das Array auf, notiere Schritt für Schritt, wie sich der Inhalt des Arrays und von i und j ändert, vielleicht für eine Eingabe von 20. Lies diesen Artikel: dummschwaetzer schrieb: > https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes Möglichkeit 2: Es sind keine Hausaufgaben, du beschäftigst dich damit komplett freiwillig. In diesem Fall lautet die Antwort: Such dir etwas besseres. Dieser Code ist umständlich und inkonsistent geschrieben und schlecht formatiert. Die Bezeichner sind nicht sprechend. Wenn das jemand absichtlich so gemacht hat, damit du nachdenken musst, ist das (in Grenzen) in Ordnung. Ansonsten willst du von dieser Quelle nichts lernen.
Taw U. schrieb: > dummschwaetzer schrieb: >> https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes > > > Wie merkt man das anhand des codes, also womit wird das Sieb angewendet, > bzw. was wird wo gemacht ? Das ist eine sehr interessante Frage. Eine der wichtigen Fähigkeiten, beim programmieren ist, sich vorstellen zu können, was geschieht. Gehe das Programm einfach Schritt für Schritt durch. Man (und ich tue das auch oft) kann auch Papier hernehmen und sich das aufschreiben und Zeichnungen machen. Ich schlage Dir vor und rate Dir sehr dazu, das zu versuchen und ggf. hier zu zeigen. Dann kann man ggf. korrigieren oder sonstigen Rat geben. Mit durchschnittlicher Schulbildung wirst Du eigentlich auch in der Lage sein, zu benennen, was das Ergebnis ist - selbst wenn Dir der Begriff "Sieb des Eratosthenes" nichts sagt.
Theor schrieb: > Dann kann man ggf. korrigieren oder sonstigen Rat geben. Oder einfach mal die eigene Birne benutzen.
Wenn ich ein Compiler wäre, würd ich verschrumpeln und sofort aus Deinen Computer springen. --- SYNTAX ERROR!! --- Denn auch in C sollte man seine Variablen deklarieren und mit vernünftigen Typen-Tags versehen. Was ist denn zum beispiel die eingabe? Ein Sack Kartoffeln? Ein Glas Wasser? Oder ein int, oder long? Vielleicht soll sie die obere Grenze festlegen bis zu der alle Primzahleen gesucht werden sollen? Bevor ich das prog compiliren kann, muß die Syntax stimmen! :-P mfg
> Wie merkt man das anhand des codes, > also womit wird das Sieb angewendet, bzw. was wird wo gemacht ? Der Code enthält das Schlagwort "Primzahl". Dadurch weiß man schon erstmal ziemlich genau worum es geht (da insbesondere große Primzahlen schwer zu finden sind). Das Sieb des Eratosthenes ist ein bekannter Algoritmus zur Primzahlsuche, eine von zwei gängigen Möglichkeiten. Bildlich gesprochen füllt man ein Array mit allen Zahlen zwischen 2 und X (oder mit Markern, die für die Zahlen stehen) und löscht daraus wiederholt alle Zahlen, die durch 2 bis X/2 (evtl. auch nur X/3) teilbar sind (und das Ergebnis nicht der Teiler selber ist). Also erst alles was durch 2 teilbar ist (dadurch wird schnell klar, daß es keine geraden Primzahlen geben kann), das trifft jede zweite Zahl. Danach alles was durch 3 teilbar ist, das trifft jede dritte Zahl, dann durch 4 eliminiert jede vierte Zahl und immer so weiter. Am Ende bleiben die Primzahlen oder Primzahlkandidaten übrig. Die andere Möglichkeit sind Primzahltests wie vor allem der LL-Test (Lucas-Lehmer) oder LLR-Test (Lucas-Lehmer-Riesel). Der LL-Test für Mersenne-Primzahlen (Format 2^n-1) macht sich dabei zunutze, daß alle Zahlen 2^n-1 binär nur aus lauter Einsen bestehen. Als Folge dieses einfachen und recht schnellen Tests (im Verhältnis zur Größe der getesteten Zahl) sind alle größten Rekord-Primzahlen soweit ich weiß Mersenne-Primzahlen gewesen. So, warum unterstellt man dir das als Hausaufgabe? Solche Algoritmen sind lange bekannt (genau wie Sortieralgoritmen) und werden daher sehr gerne als Programmierübung genutzt. Bau doch mal sowas und schau ob dein Ergebnis mit den bekannten Daten übereinstimmt. Da gibts noch viele Beispiele für sowas. Die nicht selbsterklärenden Bezeichner sind übrigens typisch für ältere Programme, da war das völlig normal. For i = ... findet man in jedem 35 Jahre alten Basic-Programm, "i" als Zähler zu nutzen war sehr beliebt. Auf i folgt im Alphabet j, also j als zweiter Zähler auch durchaus beliebt. Man hat vorausgesetzt, daß ein Programmierer sowas erkennt bzw. lesen kann - heute soll jeder Doof den Quellcode lesen können, "jeder kann programmieren" bzw. die Programmierung als Job ist lange nicht mehr so anspruchsvoll wie vor 35 Jahren - also muß/soll man selbsterklärende Bezeichnungen für Variablen verwenden, die man möglichst auch selbst noch nach 2..3 Jahren eindeutig versteht. Das ist manchmal gar nicht so einfach, "zaehler1" und "zaehler2" sind nicht besser als "i" und "j".
1 | //hier noch ein ARRAY array[eingabe+1]
|
2 | //dieses Array mit 1 füllen
|
3 | for (i = 2; i <= eingabe; i++) |
4 | {//äussere Schleife von 2 bis eingabe |
5 | if (array[i] == 1)//diese Zahl ist primzahl |
6 | {
|
7 | int j = i * 2;//erstmal das doppelte von i |
8 | while (j <= eingabe)//solange j kleiner Array_index_max |
9 | {
|
10 | array[j] = 0;//diese Zahl ist keine Primzahl |
11 | j = j + i;// n*i+i also (n+1)* i, ist dann auch keine Primzahl |
12 | }
|
13 | //Array index_max erreicht
|
14 | }
|
15 | //else diese zahl ist keine Primzahl, übergehen
|
16 | }
|
17 | //Ausgabe
|
18 | printf ("\nDie Primzahlen lauten: \n"); |
19 | for (int i = 2; i <= eingabe; i++)Schleife von 2 bis eingabe |
20 | {
|
21 | if (array[i]) |
22 | {//wenn im array an positioni keine 0 steht ist es eine Primzahl |
23 | printf ("%d, ", i); |
24 | }
|
25 | }
|
dein Algo hier nutzt aber nicht die im Wikipedia-Artikel erwähnten Features zur verkürzung der Schleifen.
Ben B. schrieb: > und löscht daraus wiederholt alle Zahlen, die durch 2 bis X/2 (evtl. > auch nur X/3) teilbar sind Oder nur bis Wurzel (X)
Und man braucht nur die Zahlen nehmen, die noch drin sind. Bis 100 also 2, 3, 5, 7. Weil 4, 6, 8 und 9 schon raus sind, bevor sie dran sind.
>Und man braucht nur die Zahlen nehmen, die noch drin sind.
macht doch
if (array[i] == 1)//diese Zahl ist primzahl
{}
//else diese zahl ist keine Primzahl, übergehen
dummschwaetzer schrieb: > macht doch > if (array[i] == 1)//diese Zahl ist primzahl > {} > //else diese zahl ist keine Primzahl, übergehen Der Code ja. Meins war Ergänzung zu Bens Erklärung Ben B. schrieb: > Danach alles was durch 3 teilbar ist, das trifft jede dritte Zahl, dann > durch 4 eliminiert jede vierte Zahl und immer so weiter.
Theor schrieb: > Eine der wichtigen Fähigkeiten, beim programmieren ist, sich vorstellen > zu können, was geschieht. Man nennt das auch "Analytisches Verständnis". So habe ich 1998 angefangen, als ich mich in VBA eingearbeitet habe. Fremden Code genommen, "analysiert" und dann nachgebaut. Das mache ich auch heute noch so, obwohl ich kein englisch kann und die meisten Seiten auf englisch sind (da muss ich mich immer "irgendwie durchmogeln").
Yep, ich hab nur versucht, die denkbar einfachste Variante darzustellen. Optimierungen machen die Sache gleich wieder komplizierter, weil man jedes Mal darstellen muß warum der Algoritmus trotzdem noch korrekte Ergebnisse liefert. Der einfachste Ansatz ist da noch schnell und logisch zu erklären weil klar erkennbar ist, daß es bei Teilern oberhalb von X/2 kein ganzzahliges Ergebnis außer 1 (bei Teiler=X) mehr geben kann und das kürzt auch gleich mal die Hälfte aller Durchläufe raus (evtl. nicht die Hälfte an Rechenzeit, da das Sieb je nach Methode bei großen Zahlen schneller wird). Wenn man jetzt drangeht die wirkliche optimale Grenze zu suchen, oberhalb der die Suche keinen Sinn mehr macht oder wieso man bereits elimierte Zahlen(folgen) bei der Suche auslassen kann, sollte man entweder eine Vorlesung über Primfaktorzerlegung besuchen oder sich das Array mal bildlich nach jedem Schleifendurchlauf darstellen lassen. Dann fällt auf, daß man z.B. mit einem Schleifendurchlauf mit Teiler 9 (einer Zahl, die bereits durch die 3 eliminiert wurde) keinen einzigen Treffer mehr hat. Alle möglichen Kandidaten wurden bereits durch die 3 eliminiert, da 9 durch 3 teilbar ist. Ich finde sowas muß man sich selbst erarbeiten wenn man sich ernsthaft für das Thema Primfaktorzerlegung interessiert. Übrigens, sollte es irgendwem gelingen, einen sehr effizienten Algoritmus zur Primfaktorzerlegung großer Zahlen zu finden, schießt der damit eine gewaltige Delle in die Sicherheit aller gängigen Verschlüsselungsmethoden mit öffentlichem und privaten Schlüssel (RSA) rein.
A. S. schrieb: > Der Code ja. Meins war Ergänzung zu Bens Erklärung Dann zitier vernünftig! Einen Text ohne Bezug hinklatschen ist dämlich.
IT-Abteilung schrieb: > Dann zitier vernünftig! Einen Text ohne Bezug hinklatschen ist dämlich. Das stimmt. Ich habe zwar zitiert, jedoch dazwischen einmal abgeschickt. Die Beiträge stehen untereinander.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.