primzahl rechnungsprogramm in C schreiben
wir müssen ein consol-programm mit codeblocks machen,womit wenn man eine zahl eingibt es sagt ob es eine primzahl ist oder nicht.Kein C++! und unser lehre sagt wir brauchen nur eine zählschleife und 2 mal if. ich komme nicht weiter kann mir wer helfen?
2 Antworten
Du läufst in der Schleife von 2 bis zur Zahl vor der eingegebenen Zahl. Wenn die eingegebene Zahl restlos durch die Laufvariable teilbar ist, kann es keine Primzahl sein, da sie ja mindestens 3 Teiler besitzt (1, die Zahl selbst und die gefundene)
Und falls die zu prüfende Zahl so groß sein sollte, daß das Warten zu lange dauert: Es reicht auch, wenn die Schleife von 2 bis zur Wurzel der eingegebenen Zahl läuft. (Da die Wurzel meistens eine Kommazahl ist: auf die nächstkleinere ganze Zahl abrunden.)
Du kannst diesen Test benutzen:
http://en.literateprograms.org/Miller-Rabin_primality_test_%28C%29
Oder kannst du die Zahl mit jeder Zahl Rest bilden, die kleiner als die Wurzel der Zahl ist. Das ist ganz sicher, aber langsam.