Murcks Geschrieben 9. Februar 2006 Geschrieben 9. Februar 2006 Hallo! Und wieder eine Klausuraufgabe! Aufgabe: Ein Programm schreiben, welches überprüft, ob die eingegebene Zahl eine Primzahl ist oder eben nicht. Hab ich gemacht und das Programm funktioniert und sieht folgendermaßen aus: #include <iostream.h> void main() { int num; int rest; int div; while ( true ) { int count = 0; cout << "Geben Sie eine Zahl ein: "; cin >> num; cout << endl; for ( int i = 1; i < num; i++ ) { rest = num % i; if ( rest == 0 ) count += 1; } if ( count == 1 ) cout << "Primzahl!" << endl << endl; else cout << "Keine Primzahl!" << endl << endl; } } Zusatzaufgabe: Jetzt soll dieses Programm zusätzlich folgendes machen: Wenn die eingegebene Zahl keine Primzahl ist, soll zusätzlich die Primfaktorzerlegung ausgegeben werden, z.B. 30 = 2 * 3 * 5. Hab allerdings keinen Ansatzpunkt... Diesmal darf ich nur Operatoren, If-Anweisungen, iostream.h und Schleifen (for, do-while, while) benutzen! Zitieren
TDM Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 du durchsuchst erstmal eine Zahl ob es eine Primzahl ist, wenn du dies machst, und dies keine ist, dann speicherst du dir einfach den faktoren in nem Array und gibst am Ende den Array zurück. #define MAX_PRIMFAKTOREN 255 bool isPrimzahl(int x) { int faktor = 2; while (faktor <= 7) //alternativ auch x/2 { if ((x % faktor) == 0) return false faktor++; } return true; } int* Primfaktor (int x) { int faktor = 2; int i = 0, int pnResult[MAX_PRIMFAKTOREN]; pnResult[i] = 0; //erste auf 0 setzen falls es doch eine Primzahl ist while (faktor < (x/2)) { if ((x % faktor) == 0) if (isPrimzahl(faktor)) pnResult[i] = faktor; i++; faktor++; } return pnResult; } Zitieren
Murcks Geschrieben 10. Februar 2006 Autor Geschrieben 10. Februar 2006 Naja, Arrays darfste net benutzen... Zitieren
Klotzkopp Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 while (faktor <= 7) //alternativ auch x/2"Alternativ" ist gut. <= 7 ist schlicht falsch. 143 ist keine Primzahl. int i = 0, int pnResult[MAX_PRIMFAKTOREN]; ... return pnResult;Aua, aua. Du gibst die Adresse einer lokalen Variablen zurück -> Bumm. Dein Algorithmus liefert außerdem keine Primfaktorzerlegung, sondern eine (unvollständige) Teilerliste, verteilt in dem Array zwischen vielen uninitialiserten Werten. Zitieren
Klotzkopp Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Naja, Arrays darfste net benutzen... Muss man auch nicht. Wie würdest du denn eine Primfaktorzerlegung von Hand machen? Das ist meist kein schlechter Ansatz für einen Algorithmus. Zitieren
TDM Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 "Alternativ" ist gut. <= 7 ist schlicht falsch. 99 ist keine Primzahl. 99 ist ja durch 3 teilbar also würde der da schon zurückgeben, dass es keine ist. Alle zahlen die keine Primzahlen sind setzen sich aus 2, 3, 5 und 7 zusammen, ansonsten ist es eine Primzahl Aua, aua. Du gibst die Adresse einer lokalen Variablen zurück -> Bumm. Dann halt return *pnResult; das ist keine unvollständige teilerlist... alles was eine valide zahl ist, ist ein Primzahlfaktor (gut, man hätte den Array vorher mit 0 füllen können...) Zitieren
Klotzkopp Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 99 ist ja durch 3 teilbar also würde der da schon zurückgeben, dass es keine ist. Alle zahlen die keine Primzahlen sind setzen sich aus 2, 3, 5 und 7 zusammen, ansonsten ist es eine Primzahl Ich habe den Fehler bemerkt, und die Zahl auf 143 geändert. Du bist dran. Dann halt return *pnResult;Damit gibst du nur den ersten Eintrag des Arrays zurück. Da steht entweder 2 oder (bei ungeradem x) ein uninitialiserter Wert drin. das ist keine unvollständige teilerlist... alles was eine valide zahl ist, ist ein Primzahlfaktor (gut, man hätte den Array vorher mit 0 füllen können...)Dein Algorithmus liefert mehrfach auftretenden Primfaktoren aber nur einmal. Zitieren
UltimateRuppi Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Die Primfaktorzerlegung gestaltet sich am einfachsten, wenn bereits Primzahlen bekannt sind. Dann kann man sich einfach von den kleinen Primzahlen zu de nhohen als Faktoren durchhangeln. Das hat den Vorteil, dass man vorher nicht noch überprüfen ob der Faktorkandidat auch eine Primzahl ist 1. Array mit Primzahlen füllen (wenn nicht erlaubt, dann musst Du halt wirklich jede überprüfen) 2. zu Faktorisierende zahl durch erste Primzahl des array teilen 3. ist die division aufgegangen? JA => Die Primzahl ist ist ein Primfaktor der Zahl (also Counter für den Wert erhöhen und zu punkt zwei gehen (mit dem divisionsergebnis als neue zahl)) NEIN => Primzahl ist kein Primfaktor (Counter auf 0 setzen, und bei 2. mit nächster primzahl weiter (Zahl ist das letzte bekannte divisionsergebnis ohne Rest) die schleife ist abbzubrechen wenn das divisionsergebnis 1 ist. ich hoffe das ist so verständlich, ich möchte den Quellcode hier, zumindest noch nicht, posten Zitieren
TDM Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Ich habe den Fehler bemerkt, und die Zahl auf 143 geändert. Du bist dran. Wie kommst du auf 143 ? O.o Zitieren
Klotzkopp Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Wie kommst du auf 143 ? O.o Das ist die kleinste Zahl, die nicht durch 2, 3, 5 oder 7 teilbar ist, aber trotzdem keine Primzahl ist - außer nach deiner "Definition". 143 = 11 * 13 Ich merke gerade, 121 hätte es auch getan. Zitieren
Guybrush Threepwood Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Eine Primzahl würde ich so ermitteln: bool Primzahl(const unsigned int &iZahl) { if (iZahl<2) return false; if(iZahl==2 || iZahl==3) return true; if (iZahl%2==0) return false; for(unsigned int i=3;i*i<=iZahl;i+=2) if(iZahl%i==0) return false; return true; } [/PHP] Zitieren
TDM Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 ok, stimmt... ich mag solche Früh-morgens-Aufgaben nicht naja... ich hab mal bissl rumgetestet mal sehen ob du wieder Fehler findest Klotzkopp (kann ich nur draus lernen :floet: ) bool teilt (int n, int t); bool prim (int n); int potenz (int n, int p); int main () { int n; int count = 0; cin >> n; cout << "Primfaktoren von " << n << "\n"; for (int i=2; i<n; ++i){ if (teilt (n, i) && prim (i)) { cout << i << " hoch " << potenz (n, i) << "\n"; ++count; } } if (count == 0) cout << n << " ist eine Primzahl\n"; else cout << endl; } bool teilt (int n, int t) { return (n % t == 0); } bool prim (int n) { if (n == 2) return true; for (int i = 2; i<n; ++i) { if (teilt (n, i)) return false; } return true; } int potenz (int n, int p) { int i = 0, pp = 1; while (teilt (n, pp)) { ++i; pp *= p; } return i-1; } müsste eigentlich gehen... bei mir funzt es jedenfalls (angelehnt an UltimateRuppi's Vorschlag) Zitieren
UltimateRuppi Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 ok hier meine lösung Erzeugung des PRimzahlenarrays: int sieve(long* anPrimes, int nSieveSize) { int nPrimesFound; bool bIsPrime; int i, p; int sq; anPrimes[0] = 2; anPrimes[1] = 3; nPrimesFound = 2; for (i = 5; i <= nSieveSize; i += 2) { p = i % 6; if ( (p == 1) || (p == 5) ) { bIsPrime = true; sq = sqrt(i); for (p = 0; anPrimes[p] <= sq; p++) { if ((i % anPrimes[p]) == 0) { bIsPrime = false; break; } } if (bIsPrime) { anPrimes[nPrimesFound++] = i; } } } return nPrimesFound; } [/PHP] Und die Zerlegung in die Faktoren [PHP] void factor(int nZahl, long* lpPrimes, int nPrimeCount) { int nWork = nZahl; int nFact = 1; int i = 0; int nFactCnt; bool b = true; printf ("%d = ", nZahl); nFactCnt = 0; while (nWork > 1) { if (i >= nPrimeCount) { printf("\t- not enough primes to complete operation!"); break; } if ((nWork % lpPrimes[i]) == 0) { nFactCnt++; nFact *= lpPrimes[i]; nWork /= lpPrimes[i]; } else { if (nFactCnt == 1) { if (i > 0) { printf(" * "); } printf("%d", lpPrimes[i]); } else if (nFactCnt > 1) { if (i > 0) { printf(" * "); } printf("%d^%d", lpPrimes[i], nFactCnt); } nFactCnt = 0; i++; } } if (nFactCnt == 1) { if (i > 0) { printf(" * "); } printf("%d", lpPrimes[i]); } else if (nFactCnt > 0) { if (i > 1) { printf(" * "); } printf("%d^%d", lpPrimes[i], nFactCnt); } printf("\n"); } Zitieren
Klotzkopp Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 TDM: Sieht gut aus. Ich bin eher ein Freund der einfachen Lösungen #include <iostream> int main() { int n; std::cin >> n; while(n>1) { for(int t=2; t<=n; ++t) { if(n % t == 0) { std::cout << t << ' '; n /= t; break; } } } }[/code] Zitieren
UltimateRuppi Geschrieben 10. Februar 2006 Geschrieben 10. Februar 2006 Das geht für einzelne Zerlegungen auch deutlich schneller, nur wenn man tausende davon machen muss, ist die lösung mit dem vorher erstellten primzahlenarray effizienter. Bei meiner Zerlegung geht viel code für die schöne formatierte ausgabe drauf generating primes array...finished - (664579 primes found in 11469 ms). 106748928 = 2^10 * 3^6 * 11 * 13 Press any key to continue Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.