Entwickler-Ecke :: Thema anzeigen - Optimieren von Primzahlenberechnung und Primfaktorenzerlegun

thD - Di 10.11.09 21:34
Titel: Optimieren von Primzahlenberechnung und Primfaktorenzerlegun

hi leute, hab mich heute in diesem forum angemeldet da ich seit ca einem monat c# programmiere und einige fragen habe

hab ein konsolenprogramm geschrieben, zum primzahlen berechnen und anschließend eine gewünschte zahl in die faktoren zu zerlegen

meine fragen:
-wie könnte man dieses programm optimieren?
-was würdet ihr ganz anders machen? warum?

danke schon mal für alle antworten

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:

        static void Main(string[] args)
        {
            int zahl, anfangszahl;
            int a = 0;
            bool zerlegung = true;
            List<int> prim = new List<int>(10000);
            List<int> faktoren = new List<int>(10000);
            

            Console.Write("Welche Zahl soll in ihre Primfaktoren zerlegt werden? ");
            zahl = anfangszahl = int.Parse(Console.ReadLine());

            prim.Add(2);

            for (int i = 2; i <= zahl; i++)
            {
                for (int j = 2; j < i; j++)
                {
                    if (i % j == 0)
                        break;

                    if (i == j + 1)
                        prim.Add(i);
                }
            }


            prim.TrimExcess();


            while (zerlegung == true)
            {
                for (a = 0; a < prim.Count; a++)
                {
                    if (zahl % prim[a] == 0)
                    {
                        faktoren.Add(prim[a]);
                        zahl /= prim[a];
                    }
                }
                if (zahl == 1)
                    zerlegung = false;
            }


            faktoren.TrimExcess();
            faktoren.Sort();
            

            Console.WriteLine("Die Zahl {0} in ihre Primzahlen zerlegt:", anfangszahl);
            foreach (int i in faktoren)
                Console.Write(i + " ");
            Console.WriteLine();

        }

Moderiert von Christian S.: Topic aus C# - Die Sprache verschoben am Di 10.11.2009 um 20:37

Kha - Di 10.11.09 23:20

:welcome:

thD hat folgendes geschrieben :

-wie könnte man dieses programm optimieren?

Erst einmal musst du die Primzahlen natürlich nicht separat speichern, wenn du sowieso nur eine einzige Zahl zerlegen willst, aber das war wohl eher zur Übung. Für beide Berechnungen gibt es noch diverse [http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes] schnellere [http://en.wikipedia.org/wiki/Integer_factorization#Special-purpose] Algorithmen; das Sieb des Eratosthenes würde ich mir auf jeden Fall einmal anschauen.
Ansonsten lässt sich dein bisheriger Code auch noch etwas optimieren: Überlege dir, wie viele Primzahlen du überhaupt brauchst, ob du nicht die bisher gefundenen bei der Suche schon benutzen kannst und ob du die Faktoren nicht auch gleich sortiert extrahieren kannst. Dann fällt auch die "zerlegung"-Variable weg.

thD hat folgendes geschrieben :

-was würdet ihr ganz anders machen?

Auf jeden Fall sollten beide Berechnungen jeweils in eine separate Methode ausgelagert werden. Noch ein paar Kleinigkeiten:

Variablen erst dann deklarieren, wenn du sie zum ersten Mal benutzt
Überlass den Listen doch selbst das Managen ihrer Kapazität. Und TrimExcess habe ich auch noch nie benutzt ;)

thD - Di 10.11.09 23:47

Zitat:

das Sieb des Eratosthenes würde ich mir auf jeden Fall einmal anschauen.

das sieb werde ich mir mal ansehen

Zitat:

Ansonsten lässt sich dein bisheriger Code auch noch etwas optimieren: Überlege dir, wie viele Primzahlen du überhaupt brauchst, ob du nicht die bisher gefundenen bei der Suche schon benutzen kannst und ob du die Faktoren nicht auch gleich sortiert extrahieren kannst. Dann fällt auch die "zerlegung"-Variable weg.

ich werde mich gleich an die arbeit machen

Zitat:

Variablen erst dann deklarieren, wenn du sie zum ersten Mal benutzt

ist das übersichtshalber oder hat das sonst noch einen grund?

Zitat:

Überlass den Listen doch selbst das Managen ihrer Kapazität. Und TrimExcess habe ich auch noch nie benutzt

ich dachte wenn man die listen vorherbestimmt liegt das alles hintereinander und somit hat man mehr geschwindigkeit?
arbeitet der compiler die leeren nicht ab?

Kha - Mi 11.11.09 00:47

thD hat folgendes geschrieben :

Zitat:

Variablen erst dann deklarieren, wenn du sie zum ersten Mal benutzt

ist das übersichtshalber oder hat das sonst noch einen grund?

Vor allem ist es in C-artigen Sprachen einfach Standard ;) . Aber ja, ich finde es persönlich so übersichtlicher. Von einer Schleifenvariable will ich außerhalb der Schleife nichts mitbekommen.

thD hat folgendes geschrieben :

ich dachte wenn man die listen vorherbestimmt liegt das alles hintereinander und somit hat man mehr geschwindigkeit?

List<T> ist nur ein Wrapper um ein einzelnes Array, und die liegen immer lückenlos im Speicher.

thD hat folgendes geschrieben :

arbeitet der compiler die leeren nicht ab?

Wie meinen?

thD - Mi 11.11.09 11:52

Zitat:

thD hat folgendes geschrieben :
arbeitet der compiler die leeren nicht ab?
Wie meinen?

also ich habe mal gelesen das, wenn eine ArrayList voll ist, sich die Kapazität verdoppelt
ich dachte List<> funktioniert so ähnlich wie eine ArrayList und wenn sich die Kapazität verdoppelt, dann würden da einige leer bleiben
wenn ich jetzt mit einer schleife alles durchlaufe müssten auch die leeren kontrolliert werden, oder ist das nicht so?

hab mir das mit dem Sieb angesehen:
sehr effektiver code =)

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

        static void Main(string[] args)
        {
            Console.Write("Wie weit sollen die Primzahlen berechnet werden? ");
            ulong ende = ulong.Parse(Console.ReadLine());
            bool[] zahlen = new bool[ende];
            List<ulong> prim = new List<ulong>();

            for (ulong i = 2; i < ende; i++)
                zahlen[i] = true;

            for (ulong i = 2; i < ende; i++)
            {
                if (zahlen[i] == true)
                {
                    for (ulong j = i * i; j < ende; j += i)
                    {
                        zahlen[j] = false;
                    }
                    prim.Add(i);
                }
            }

            foreach (ulong i in prim)
                Console.Write(i + " ");

            Console.WriteLine();
        }

eine frage hab ich noch:
wie kann man die zeit messen, die ein programm bzw. ein programmabschnitt braucht?

Ralf Jansen - Mi 11.11.09 12:09

Zitat:

ich dachte List<> funktioniert so ähnlich wie eine ArrayList und wenn sich die Kapazität verdoppelt, dann würden da einige leer bleiben
wenn ich jetzt mit einer schleife alles durchlaufe müssten auch die leeren kontrolliert werden, oder ist das nicht so?

Das mit dem verdoppeln ist korrekt. Aber die unbenutzten Indizes im Array existieren nur Klassenintern und haben nach außen eigentlich keine Auswirkung. Der Enumerator wird einfach nur bis zur Befüllungsgrenze des Arrays über dieses iterieren die ~leeren~ Teile dahinter sind egal.

Zitat:

wie kann man die zeit messen, die ein programm bzw. ein programmabschnitt braucht?

Hilfreich ist da z.b. die Stopwatch [http://msdn.microsoft.com/de-de/library/system.diagnostics.stopwatch.aspx] Klasse.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!