Primzahlen ausgeben
-
Also zum einen Rauche ich nichts zum anderen habe ich mir andere Codes angeschaut, danke -.-
inzwischen hab ich viel rumprobiert und komme auf folgenden, funktionierenden Code
#include <iostream> using namespace std; int main() { int zahl=0; cout << "Bitte geben Sie eine Zahl ein: " << endl; //Einlesen der Zahl cin >> zahl; //Übergabe der Eingabe an Zahl for (int teiler=2; teiler<=zahl; teiler++) //Solange teiler kleiner/gleich zahl { bool isPrime = true; // Annahme Prime ist immer gegeben for (int teiler2=2; teiler2<teiler; teiler2++) // Solange Teiler des Teilers kleiner { //Vorsicht KEIN <= benutzen!!! if (teiler%teiler2==0) // Teilung des Teilers durch seinen Teiler { // ohne Rest bedeutet es ist keine Primzahl isPrime = false; } } if (isPrime == true) { cout << teiler << " "; } } cout << endl; system("PAUSE"); return 0; }Das Problem ist, ich kam darauf durch probieren und vergleichen, nur wieso
for (int teiler2=2; teiler2<teiler; teiler2++) // Solange Teiler des Teilers kleiner { //Vorsicht KEIN <= benutzen!!! if (teiler%teiler2==0) // Teilung des Teilers durch seinen Teiler { // ohne Rest bedeutet es ist keine Primzahl isPrime = false; } }den Teiler eben auf KEINE Primzahl stellt ist mir unklar... ich raff das einfach nicht.
-
sorry hat sich erledigt ich raffs jetzt endlich -.- schwere Geburt... sorry.
-
prime schrieb:
wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...
Du hast offensichtlich nicht verstanden, was eine Primzahl ist.
-
"also das ganze von unskilled kommt der geforderten Lösung die ich raushaben "soll" am nähesten"
Gut ^^"ist mir aber total unschlüssig"
Ich hab doch extra alles kommentiert?!"Wieso eigentlich zahl/2"
Schon mal nen Teiler gesehen, der größer ist, als die Hälfte der Zahl? a*b=c => c >= 2, b >= 2"und wieso ist es keine Primzahl wenn die zahl durch i geteilt keinen Rest hat?"
omg... kein Rest => ist teilbar => ist keine Primzahl (da die ja nur durch sich selbst und 1 teilbar ist...)"potentielle Primzahl"
Es gibt einfach ma keine potentiellen Primzahlen? Oder wann ist eine Zahl potentielle Primzahl? Oo Wenn sie ungerade ist? Oder erst, wenn die Quersumme nicht mehr durch 3 teilbar ist oder wann?"eine Primzahl ja ohne Rest teilbar sein muss?"
Omg... Genau das macht eine Primzahl doch aus - das sie NICHT teilbar ist... xD"Bei meinem Code komme ich nicht weiter, ich bekomme einfach die Unterscheidung nicht hin ob es sich dabei wirklich um eine Zahl handelt die nur durch sich selbst (und 1) teilbar ist -.-"
Ich hab dir deinen Code genau so umgeschrieben, dass es funtzt... GENAU so!!!Irgendwie weiß ich gerad nicht, ob du überhaupt ne Ahnung hast, von dem, was du machen willst: Primzahlen berechnen... Guck ma in der Definition in Wikipedia dazu nach...
Ciao...
//edit;
"prime schrieb:
wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...Du hast offensichtlich nicht verstanden, was eine Primzahl ist. "
Was daran falsch? Er muss eigtl nur 2-7 überprüfen (hat er ja au berichtigt) - aber ich kann da keinen Fehler finden : P Auf den Threadersteller hingegen trifft es 100pro zu...
-
Konrad Rudolph schrieb:
prime schrieb:
wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...
Du hast offensichtlich nicht verstanden, was eine Primzahl ist.
Entweder bist du zu voreilig und hast den Nachpost nicht gelesen oder ich hab nicht verstanden was eine Primzahl ist.
-
prime schrieb:
Konrad Rudolph schrieb:
prime schrieb:
wobei du nur von 1 - 7 überprüfen musst, denn 8 und 9 sind Vielfache von 2 und 3 ...
Du hast offensichtlich nicht verstanden, was eine Primzahl ist.
Entweder bist du zu voreilig und hast den Nachpost nicht gelesen oder ich hab nicht verstanden was eine Primzahl ist.
Das Nachposting macht's nicht besser. Es reicht einfach nicht, die Zahlen 2–7 zu prüfen. Man muss jeden möglichen Teiler prüfen.
Eine Primzahl ist ja als Zahl definiert, die nur durch sich selbst und durch 1 teilbar ist. Nach Deinem Code würde die Definition lauten „eine Zahl, die nicht durch die Zahlen 2–7 teilbar ist.“
Und ich liefere auch gleich ein Gegenbeispiel: Dein Code würde ausgeben, dass 121 eine Primzahl ist, dabei ist 121 durch 11 teilbar.
-
ich hab auch mal so ein Programm geschrieben. Hier ist meine Version(hat zwar noch einige Bugs)
#include <iostream> using namespace std; bool istPrimzahl(int zahl) { int i; float temp; for(i = 2; i<zahl-1; i++) { temp = zahl%i; if (temp == 0) return false; }; return true; }; int main(int argc, char *argv[]) { int z, bis; bool test; cout << "Geben sie ein bis wohin sie die Primzahlen angezeickt bekommen wollen:" << endl; cin >> bis; z = 3; while(z!=bis) { test = istPrimzahl(z); if (test == true) cout << z << endl; z++; }; system("PAUSE"); return EXIT_SUCCESS; }
-
Auch EXIT_SUCCESS ist in stdlib definiert.-Also "#include <cstdlib>".
-
Mein Code denn ich gestern gepostet habe, hat übrigens noch einen Fehler:
for(int teiler=2;teiler<=grenzwert;teiler++)und nicht
for(int teiler=2;teiler<=9;teiler++)Vollständig und richtig also:
#include <iostream> int main(void) { std::cout<<"Grenzwert: "; int grenzwert; std::cin>>grenzwert; fflush(stdin); //Jede Ganzzahl zwischen 2 und dem benutzerdefinierten Grenzwert koennte eine Primzahl sein, //weshalb in der Folge jede durchgetestet wird. for(int potenzielle_primzahl=2;potenzielle_primzahl<=grenzwert;potenzielle_primzahl++) { bool ist_primzahl=true; //Ist die potenzielle Primzahl auch durch eine andere Zahl als 1 und sich selbst teilbar? for(int teiler=2;teiler<=grenzwert;teiler++) { if(potenzielle_primzahl%teiler==0&&potenzielle_primzahl!=teiler) ist_primzahl=false; } if(ist_primzahl==true) std::cout<<potenzielle_primzahl<<std::endl; } std::cin.get(); }
-
Ich hab so was auch mal geschrieben - zwar schon ewig her aber es ist toll
Wobei man Primzahlen besser nur auf die Teilbarkeit durch Primzahlen prüft - ist schneller, als durch jede Zahl wieder versuchen zu teilen ^^So ist übrigens sehr viel schneller, als deine Variante:
unsigned int to = 1; for (__int64 i = 3; i < 1347890000000; i+=2) { if (to*to <= i) ++to; bool isprim = true; unsigned __int32 teil = 0; while ((isprim) && (teiler[teil] < to)) { if (i%teiler[teil] == 0) { isprim = false; } teil++; } //.... }teiler[....] ist nen Array von Primzahlen - somit wird bei jeder Zahl also nur geguckt, ob sie durch eine Primzahl teilbar ist...
-
die primzahlen im array müssen aber auch erstmal berechnet werden. Wie machst du das dann? noch ein array mit noch kleineren Primzahlen? aber wie hast du das dann berechnet?
Das mit dem array ist prinzipiell eine gute idee, aber nicht so gut, wenn man nur begrenzten Speicher hat. Also entweder schnelles Rechnen, oder geringer Speicherverbrauch.
-
so:
unsigned __int32 teiler[90100]; unsigned __int32 a = 0; unsigned __int32 to = 1; for (unsigned __int32 j = 3; j < 1160990; j+=2) { if (to*to <= j) ++to; bool isprim = true; unsigned __int32 teil = 3; while ((isprim) && (teil < to)) { if (j%teil == 0) { isprim = false; } teil += 2; } if (isprim) teiler[a++] = j; }Naja.. Speicher... nicht mal 352KB... Also für das Array mit den Primzahlen (90100*32/8/1024 == 351,...)
Und da das Prog den PC so und so zu ~100% auslastet ists auch egal, wie viel RAM ungenutzt bleibt - nebenbei kann man eh nix mehr machen ;o) (na k - wenn man 2 CPUS hat dann geht das schon - aber mal ehrlich... Was ist das heut zu Tage schon noch?Ciao : )
-
naja, das war ein recht schlechtes Beispiel, um zu zeigen, dass man manchmal vor der Wahl zwischen Speicherverbrauch und Rechenzeit steht, aber überleg mal, was passieren würde, wenn man nicht die Primzahlen unter 2^32-1, sondern z.B. die Primzahlen unter 2^2000000 ausrechnen wollte. Dann wären das andere Größenordnungen als einige kilobyte
-
Kann einfach mal einer die Primzahlen hochladen, dann muss sie nicht jeder immer wieder ausrechnen.
-
In der Größenordnung könntest du auch so nichts mehr mit den Mitteln anfangen... Du müsstest dir ne eigene Zahlenklasse schreiben und dort das addieren, multiplizieren und dividieren implementieren... btw würde ich gerade in solchen Größenordnungen diese Lösung bevorzugen!
/edit:
Auch dann ist es noch schneller - man muss diese Primzahlen eben nur Stück für Stück speichern und wieder durch andere überschreiben und wieder neu berechnen...bb
-
(Es ging ursprünglich nicht darum einen möglichst "schlauen" Algorithmus zu implementieren, sondern einen möglichst einfachen in Bezug auf das Verständnis.)
-
So, nun auch mein Programmcode zu diesem Thema.
Ein paar einleitende Worte zu Mathematik.
Als erstes braucht man nur ungerade Zahlen zu testen, alle gerade sind mindestens in den Primfaktor 2 zu zerlegen und damit definitiv keine Primzahl. Es ist nur sinnvoll Primzahlen zum Testen zu verwenden, und man braucht nur die zu nehmen die kleiner oder gleich der Wurzel der zu testenden Zahl sind. (p*p <= i) Wenn wir einen Primfaktor gefunden haben, können wir den Test auf Teilbarkeit abbrechen, da die Zahl nicht prim ist.Es wird der Datentyp long long verwendet, was nicht ISO konform ist. Wenn es nicht funktioniert durch long ersetzen.
#include <ostream> #include <iostream> #include <vector> int main() { std::size_t const MAX_ELEM = 10000000; long long const max = 10000001; std::vector<long long> primes; primes.reserve(MAX_ELEM); primes.push_back(2); primes.push_back(3); // Edit: Index angepaßt // Sorry: Man sollte den Code nicht auf der Webseite schreiben for (long long i = 5; i != max; i+=2) { long long test (1); bool p (true); while (p && ((primes[test]*primes[test]) <= i)) { if (0 == (i % primes[test++])) { p = false; break; } } if (true == p) { primes.push_back(i); } } std::cout << primes.size() << " Primzahlen gefunden\n"; std::cout << "Alle Primzahlen bis " << max << "\n"; for (std::vector<long long>::const_iterator it(primes.begin()), en(primes.end()); it != en; ++it) { std::cout << *it << "\n"; } }
-
Joar - danke ^^
das hatte sich ja aber angeblich geklärt... er meinte ja, er hats jz (wahrscheinlich hat er es einfach sein lassen, aber das is ne mein prob
)zum thread an sich:
es wäre eben au darum gegangen, sich zumindest mit dem thema primzahlen zu beschäftigen... er wusste weder was das ist, noch wie das geht...egal - closed nehm ich einfach ma an ^^
tomps: shift is doof ^^
//edit:
@john:
1. Du hast die 3 zweimal in dem Array drin...
2. Is eigtl komplett mein Algorithmus - nur ineffektiver : P
-
unskilled schrieb:
//edit:
@john:
1. Du hast die 3 zweimal in dem Array drin...
2. Is eigtl komplett mein Algorithmus - nur ineffektiver : P<Edit> Geschriebene (bei mir ausgeführte) und gepostete Version unterschieden sich voneiander.
Nein, die 3 kommt nur einmal drin vor, liegt an den Testbedingungen.
</Edit>
Als ich das eingegeben habe, hattest Du noch nicht gepostet.
Nein, dein Algorithmus nimmt alle ungerade Zahlen als Testzahlen, das ist deutlich langsamer, wenn man hinreichend große Zahlen hat.P.S. Wenn es richtig große Zahlen sein sollen, sollte man sich das hier durchlesen http://de.wikipedia.org/wiki/Zahlkörpersieb
-
loooooooooooool...
1. "die 3 kommt nur einmal drin vor"
primes.push_back(3); for (long long i = 3; i != max; i+=2) // i == 3 { long long test (1); bool p (true); while (p && ((primes[test]*primes[test]) <= i)) { //p == true; primes[1] == 3 ==> primes² == 9 => false => abbruch if (0 == (i % primes[test++])) { p = false; break; } } if (true == p) // p == TRUE!!!! primes.push_back(i); //PUSH_BACK (3) }2. "Als ich das eingegeben habe, hattest Du noch nicht gepostet."
Hast du 6 Stunden gebraucht? xD
14.30 und 15.07Uhr ich) / 21.40Uhr (du) oder so waren die Zeiten : P3. "Nein, dein Algorithmus nimmt alle ungerade Zahlen als Testzahlen, das ist deutlich langsamer, wenn man hinreichend große Zahlen hat."
Glaub ich nicht dran.... (siehe das Posting 14.30Uhr)
Du nimmst vector - vector hat meines erachtens aber eine max.größe und ist langsamer, weil er ständig neuen Speicher alloziiert - mein Array hingegen ist statisch, wird immer, wenn es voll ist in ne Datei gespeichert und dann wieder von vorn gefüllt... Die Primzahlen, die ich zum Testen habe sind in nem anderen Array...Naja... Wie du meinst...
Bye Tom