primzahlen berechnen - Seite 2

Seite 2 von 3 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/primzahlen_berechnen_104423/page_2 - zur Vollversion wechseln!

Geigerzeiger schrieb am 18.01.2004 um 14:03

es soll keine int function sein sondern void!
statt dem break in zeile 6 sollte return; stehen.

Tschuldigung für diese Fehler!

Smoldi schrieb am 18.01.2004 um 20:07

das sieb des eratosthenes wird dir sicher mehr helfen als die lösung der aufgabe...

watchout schrieb am 18.01.2004 um 20:25

Zitat von Smoldi
das sieb des eratosthenes wird dir sicher mehr helfen als die lösung der aufgabe...

nur dass das halt bei den höheren zahlen nicht mehr so die optimale lösung is

Smoldi schrieb am 18.01.2004 um 20:29

eh
bis 1000 gehts aber ohne probleme
und rekursion ist nie die optimale lösung (performancemässig)

atrox schrieb am 19.01.2004 um 03:58

Zitat von Smoldi
...und rekursion ist nie die optimale lösung (performancemässig)

bitte erläutere doch mal, wieso du zu dieser meinung kommst...

um einen allgemeinen rekursiven algorithmus (zb für bäume, graphen, branch&bound, backtracking, quicksort,...) iterativ _schneller_ zu lösen muss man sich oft schon ziemlich anstrengen. nicht selten wird man irgenwelche listen mit indizes, verketete listen oder andere strukturen verwalten müssen. dagegen wird der stack von der cpu verwaltet.

die rekursion ist deutlich mächtiger als eine schleife: jede schleife läßt sich leicht in eine rekursion überführen (auch wenn das nicht immer wirklich sinnvoll erscheint), aber um rekursionen in schleifen zu überführen ist oft deutlich mehr aufwand notwendig.

MightyMaz schrieb am 19.01.2004 um 05:01

Das Problem bei Rekursionen ist, daß sie bei steigender Komplexität Speichermäßig explodieren. Es gibt zwar keine Variablen, aber der Stack wird zugemüllt (ist ja auch ein Speicher) und irgendwann gibts halt da schon mal nen overflow
Es gibt ganz wenige Ausnahemen, bei denen rekursive Lösungen mit GUTEN Iterativen gleichziehen. Besser sind sie von der Performance her praktisch nie, wenn sich schon mal jemand ne Iterative Lösung ausgedacht hat (und das ist bei Primzahlen ja der Fall ).

Es kann manchmal sehr sehr schwer sein von einer einfach hinzuschreibenden Rekursion auf eine Iteration zu kommen, aber es ist bewiesen, daß jedes Problem iterativ zu lösen ist.

mg_shadow schrieb am 19.01.2004 um 16:12

also wozu man hier eine rekursion braucht ist mir erlichgesagt nicht klar, das würd auch mit normalen schleifen gehen!
hier braucht die rekursion nur viel speicher und bringt nix!

@smoldi
das sieb ist cool!
wäre programmiertechnisch nicht wirklich komplizierter, aber ich vermute das es schneller ist!

SoulFly schrieb am 19.01.2004 um 17:12

wieso nimmst du nicht fresserettich's code?
ich hab den (ich bin der "freund" von dem er spricht) mindestens 100 mal durchgetestet ... :rolleyes:

HaBa schrieb am 19.01.2004 um 21:33

Wenn eine Rekursion gefordert ist dürfte es sich um eines dieser Anfängerbeispiele handeln bei denen ein spezieller Weg gefordert ist (nehme ich mal an) => würde auch dafürsprechen, denn welcher versierte Coder fragt nach sowas ...

BuSHidO schrieb am 20.01.2004 um 08:21

Zitat
#include <stdio.h>

int main(void)
{
int year;
int a, b;

for (year = 2001; year < 2050; year += 2)
{
a = 3;
while (a <= (b = year/a))
{
if (a*b == year)
{
printf("%d = %d * %d\n", year, a, b);
a = year;
break;
}
a += 2;
}
if (a != year)
printf ("%d is prime.\n", year);
}
return 0;
}

musst allerdings auf 1000 umschreiben ...

Geigerzeiger schrieb am 21.01.2004 um 15:04

hmm... hat aber nichts mit rekursion zu tun oder?

samuel schrieb am 27.01.2004 um 16:42

Zitat von mg_shadow
also wozu man hier eine rekursion braucht ist mir erlichgesagt nicht klar

weil dass die aufgabenstellung ist...

und rekursion kann sehr oft sehr schoene loesungen anbieten. sie ist zwar speicherlastiger, kann aber in vielen faellen um soviel schneller sein als jede iteration. (und auch vom code her einfacher verstaendlicher)

mfg sam

atrox schrieb am 27.01.2004 um 17:59

wir rätseln ja auch schon die ganze zeit, warum gerade rekursiv primzahlen berechnen,... keine angabe die die vorzüge einer rekursion deutlich macht.

HaBa schrieb am 27.01.2004 um 18:00

Ich habs eh schon weiter oben geschrieben, das roch sowas nach Vorgabe ...

alexsb schrieb am 28.01.2004 um 16:58

Also zum Thema Rekursion:
Rekursion ist wunderbar für Definitionen, aber sie ist Speicherplatzmäßig nicht optimal. Ausserdem wird von guten Compilern eine Rekursion in eine Iteration übergeleitet.

Ein Beispiel in der Rekursion katastrophale Auswirkungen auf die Laufzeit hat:
Berechnung der Fibonacci Zahlen mittels der Funktion fib()
fib(6)=fib(5)+fib(4)
=fib(4)+fib(3)+fib(3)+fib(2)
=fib(3)+fib(2)+fib(2)+fib(1)+fib(2)+fib(1)+1
....

In diesem Beispiel wird fib(3) schon 3 mal berechnet.

Also, bei Rekursionen aufpassen.