Feedback

C# - Primzahlenermittlung / Primfaktorzerlegung

Veröffentlicht von am 24.05.2013
(1 Bewertungen)
Hier ein Code-Snippet, mit welchem man ermitteln kann, ob eine Zahl prim ist oder in welche Primfaktoren sie sich zerlegen lässt.
GFU-Schulungen  [Anzeige]

VB.NET Komplett

Sie stehen vo der Aufgabe, individuelle Anwendungen für Windows zu schreiben. Hier ist VB.NET die optimale Sprache. Sie erlernt sich recht leicht und passt sich komplett in die .NET Umgebung von Microsoft ein. Nach der Schulung entwickeln Sie anwenderfreundliche Programme in VB.NET . Mit den objektorientierten Modellen in VB.NET erzeugen Sie außerdem wiederverwendbare Komponenten.

XML und .NET Überblick

Um auf dem neuesten Wissensstand zu sein, sollten Sie unser aktuelles ASP .NET Komplett Seminar belegen.
Nach dem Seminar kennen Sie die wichtigsten Strömungen in der Software-Technologie

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.IO;

namespace PrimeNumbers
{
    public static class Program
    {
        /// <summary>
        /// Bestimmt, ob eine Zahl X prim ist.
        /// </summary>
        /// <param name="number">Zahl X</param>
        /// <returns>ob eine Zahl X prim ist</returns>
        private static Boolean IsPrime(UInt32 number)
        {
            if (number < 2)
            {
                return (false);
            }
            else if (number == 2)
            {
                return (true);
            }
            else if (number % 2 == 0)
            {
                return (false);
            }
            else
            {
                List<UInt32> primes;

                return (IsPrime(number, out primes));
            }
        }

        /// <summary>
        /// Bestimmt, ob eine Zahl X prim ist 
        /// und gibt die Primzahlen bis Zahl X zurück.
        /// </summary>
        /// <param name="number">Zahl X</param>
        /// <param name="primes">die Primzahlen bis Zahl X</param>
        /// <returns>ob eine Zahl X prim ist</returns>
        private static Boolean IsPrime(UInt32 number
            , out List<UInt32> primes)
        {
            if (number < 2)
            {
                primes = new List<UInt32>(0);
                return (false);
            }
            else if (number == 2)
            {
                primes = new List<UInt32>(new UInt32[] { 2 });
                return (true);
            }
            primes = PrimeNumbersMegaOptimized(number);
            return (primes[primes.Count - 1] == number);
        }

        /// <summary>
        /// Zerlegt eine Zahl X in ihre Primfaktoren.
        /// </summary>
        /// <param name="number">Zahl X</param>
        /// <returns>die Liste der Primfaktoren</returns>
        private static List<UInt32> PrimeFactorization(UInt32 number)
        {
            if (number < 2)
            {
                throw (new ArgumentException("number"));
            }
            else
            {
                List<UInt32> primes;

                if (IsPrime(number, out primes))
                {
                    return (new List<UInt32>(new UInt32[] { number }));
                }
                else
                {
                    return (PrimeFactorization(number, primes));
                }
            }
        }

        /// <summary>
        /// Zerlegt eine Zahl X in ihre Primfaktoren.
        /// </summary>
        /// <param name="number">Zahl X</param>
        /// <returns>die Liste der Primfaktoren</returns>
        private static List<UInt32> PrimeFactorization(UInt32 number
            , List<UInt32> primes)
        {
            List<UInt32> primeFactors;

            primeFactors = new List<UInt32>(primes.Count);
            for (Int32 i = 0; i < primes.Count; )
            {
                UInt32 prime;

                prime = primes[i];
                if (number == prime)
                {
                    primeFactors.Add(prime);
                    break;
                }
                else if (number % prime == 0)
                {
                    primeFactors.Add(prime);
                    number /= prime;
                }
                else
                {
                    i++;
                }
            }
            return (primeFactors);
        }

        /// <summary>
        /// Jede Zahl lässt sich in ihre Primfaktoren zerlegen.
        /// D.h. um festzustellen, ob eine Zahl X prim ist, 
        /// müssen wir nur die Zahl testweise durch alle vorhergehenden
        /// Primzahlen dividieren. Nur wenn nie ein ganzzahliges Ergebis 
        /// herauskommt, ist die Zahl selbst prim.
        /// </summary>
        /// <param name="upTo">Zahl X</param>
        /// <returns>die Liste der Primzahlen bis Zahl X</returns>
        private static List<UInt32> PrimeNumbersStandard(UInt32 upTo)
        {
            if (upTo < 2)
            {
                return (new List<UInt32>(0));
            }
            else if (upTo < 3)
            {
                return (new List<UInt32>(new UInt32[] { 2 }));
            }
            else if (upTo < 5)
            {
                return (new List<UInt32>(new UInt32[] { 2, 3 }));
            }
            else
            {
                List<UInt32> primes;
                Int32 capacity;

                //schon ab X = 500 fällt die Primzahlquote 
                //auf 19%, eine Kapazität von 20% ist also
                //großzügig bemessen
                capacity = (Int32)(upTo / 5);
                primes = new List<UInt32>(capacity);
                primes.Add(2);
                primes.Add(3);
                for (UInt32 i = 5; i <= upTo; i += 2)
                {
                    Boolean isPrime;

                    isPrime = true;
                    for (Int32 j = 0; j < primes.Count; j++)
                    {
                        if (i % primes[j] == 0)
                        {
                            isPrime = false;
                            break;
                        }
                    }
                    if (isPrime)
                    {
                        primes.Add(i);
                    }
                }
                return (primes);
            }
        }

        /// <summary>
        /// Eine verbesserte Version von PrimeNumbersStandard().
        /// Wenn man wissen will, ob 19 prim ist (ja), dann braucht man
        /// nicht bis zur vorherigen Primzahl 17 gehen, um das 
        /// herauszufinden. Es reicht, die bis zu der Primzahl zu gehen, 
        /// die am nächsten an Zahl X geteilt durch 2 dran ist.
        /// Im Fall 19 / 2 = 9,5 --> also 7. 11 braucht nicht mehr 
        /// probiert werden, weil 11 * 2 schon 22 ist.
        /// </summary>
        /// <param name="upTo">Zahl X</param>
        /// <returns>die Liste der Primzahlen bis Zahl X</returns>
        private static List<UInt32> PrimeNumbersOptimized(UInt32 upTo)
        {
            if (upTo < 2)
            {
                return (new List<UInt32>(0));
            }
            if (upTo < 3)
            {
                return (new List<UInt32>(new UInt32[] { 2 }));
            }
            if (upTo < 5)
            {
                return (new List<UInt32>(new UInt32[] { 2, 3 }));
            }
            else
            {
                List<UInt32> primes;
                Int32 capacity;

                //schon ab X = 500 fällt die Primzahlquote 
                //auf 19%, eine Kapazität von 20% ist also
                //großzügig bemessen
                capacity = (Int32)(upTo / 5);
                primes = new List<UInt32>(capacity);
                primes.Add(2);
                primes.Add(3);
                for (UInt32 i = 5; i <= upTo; i += 2)
                {
                    Boolean isPrime;

                    isPrime = true;
                    for (Int32 j = 0; j < primes.Count; j++)
                    {
                        if (i % primes[j] == 0)
                        {
                            isPrime = false;
                            break;
                        }
                        else if (primes[j] > i / 2)
                        {
                            break;
                        }
                    }
                    if (isPrime)
                    {
                        primes.Add(i);
                    }
                }
                return (primes);
            }
        }

        /// <summary>
        /// Eine verbesserte Version von PrimeNumbersOptimized().
        /// Diese schränkt den Suchraum in den Primzahlen noch weiter ein.
        /// Wenn eine Zahl nicht durch eine andere Primzahl dividierbar ist,
        /// dann wird sie auch nicht durch eine Zahl größer als der Quotient 
        /// dieser Operation teilbar sein.
        /// 
        /// Beispiel 1: 49 (nicht prim):
        /// 
        /// 49 / 2 = 24,5
        /// höchste noch mögliche Primzahl: 23
        /// 49 / 3 = 16,333
        /// höchste noch mögliche Primzahl: 13
        /// 49 / 5 = 9,8
        /// höchste noch mögliche Primzahl: 7
        /// 49 / 7 = 7 --> nicht prim
        /// 
        /// Beispiel 2: 53 (prim):
        /// 53 / 2 = 26,5
        /// höchste noch mögliche Primzahl: 23
        /// 53 / 3 = 17,667
        /// höchste noch mögliche Primzahl: 17
        /// 53 / 5 = 10,6
        /// höchste noch mögliche Primzahl: 7
        /// 53 / 7 = 7,571 -> prim
        ///
        /// Zur Vervollständigung:
        /// 53 / 13 = 4,077
        /// 53 / 17 = 3,118
        /// 53 / 19 = 2,789
        /// 53 / 23 = 2,304
        /// 29 ist schon mehr als die Hälfte von 53, 
        /// hier ist also endgültig Schluss
        /// </summary>
        /// <param name="upTo">Zahl X</param>
        /// <returns>die Liste der Primzahlen bis Zahl X</returns>
        private static List<UInt32> PrimeNumbersSuperOptimized(
            UInt32 upTo)
        {
            if (upTo < 2)
            {
                return (new List<UInt32>(0));
            }
            else if (upTo < 3)
            {
                return (new List<UInt32>(new UInt32[] { 2 }));
            }
            else if (upTo < 5)
            {
                return (new List<UInt32>(new UInt32[] { 2, 3 }));
            }
            else
            {
                List<UInt32> primes;
                Int32 capacity;

                //schon ab X = 500 fällt die Primzahlquote 
                //auf 19%, eine Kapazität von 20% ist also
                //großzügig bemessen
                capacity = (Int32)(upTo / 5);
                primes = new List<UInt32>(capacity);
                primes.Add(2);
                primes.Add(3);
                for (UInt32 i = 5; i <= upTo; i += 2)
                {
                    Boolean isPrime;

                    isPrime = true;
                    for (Int32 j = 0; j < primes.Count; j++)
                    {
                        if (i % primes[j] == 0)
                        {
                            isPrime = false;
                            break;
                        }
                        else if (primes[j] > i / primes[j])
                        {
                            break;
                        }
                    }
                    if (isPrime)
                    {
                        primes.Add(i);
                    }
                }
                return (primes);
            }
        }

        /// <summary>
        /// Diese Methode verfolgt einen komplett anderen Ansatz.
        /// Sie basiert auf dem Sieb des Eratosthenes
        /// https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
        /// hier wird einfach das Ausschlussverfahren angewendet. 
        /// Wenn eine Zahl X prim ist, dann sind alle Vielfachen
        /// von Zahl X nicht prim.
        /// Diese Methode arbeitet alle Zahlen von n = 2 bis Zahl X
        /// ab und ermittelt alle Vielfachen von n als nicht prim.
        /// Dann wird n um eins erhöht und falls diese Zahl prim ist,
        /// werden auch davon alle Vielfachen ermittel.
        /// 
        /// Beispiel:
        /// 
        /// Der Algorithmus fängt mit 2 an und markiert die Vielfachen
        /// von 2 als nicht prim: 4, 6, 8, 10, ...
        /// Dann fährt er mit der 3 fort, die prim ist (weil sie kein
        /// Vielfaches von 2 ist) und markiert 6, 9, 12, 15, ...
        /// Dann kommt 4, dies ist aber schon als nicht prim markiert.
        /// Dann kommt 5, ...
        /// Am Ende hat man ein Array dass für jede einzelne Zahl
        /// zwischen 2 und Zahl X bestimmt hat, ob sie prim ist.
        /// 
        /// Diese Methode hat auch den Vorteil, dass Multiplizieren
        /// für einen Computer einfacher ist, als Dividieren.
        /// </summary>
        /// <param name="upTo">Zahl X</param>
        /// <returns>die Liste der Primzahlen bis Zahl X</returns>
        private static List<UInt32> PrimeNumbersUltraOptimized(
            UInt32 upTo)
        {
            if (upTo < 2)
            {
                return (new List<UInt32>(0));
            }
            else
            {
                Boolean[] isPrime;
                List<UInt32> primes;
                Int32 capacity;

                isPrime = new Boolean[upTo + 1];
                for (UInt32 i = 2; i <= upTo; i++)
                {
                    isPrime[i] = true;
                }
                for (UInt64 i = 2; i < upTo; i++)
                {
                    if (isPrime[i])
                    {
                        for (UInt64 j = i * 2; j <= upTo; j += i)
                        {
                            isPrime[j] = false;
                        }
                    }
                }
                //schon ab X = 500 fällt die Primzahlquote 
                //auf 19%, eine Kapazität von 20% ist also
                //großzügig bemessen
                capacity = (Int32)(upTo / 5);
                primes = new List<UInt32>(capacity);
                for (UInt32 i = 2; i <= upTo; i++)
                {
                    if (isPrime[i])
                    {
                        primes.Add(i);
                    }
                }
                return (primes);
            }
        }

        /// <summary>
        /// Eine verbesserte Version von PrimeNumbersUltraOptimized().
        /// 
        /// Diese vermeidet unnötige Berechnungen im unteren Feld und
        /// startet die Multiplikation erst beim Quadrat der Zahl, nicht
        /// schon beim ersten Vielfachen.
        /// 
        /// Dies vermeidet Doppelberechnungen.
        /// 
        /// Beispiel: Zahl X = 5
        /// 
        /// 2 * 5 = 10. 10 ist aber bereits durch 2 teilbar.
        /// 3 * 5 = 15. 15 ist aber bereits durch 3 teilbar.
        /// 4 * 5 = 20. 20 ist aber bereits durch 2 teilbar.
        /// 
        /// Erst 5 * 5 ist der erste sinnvolle Ausschluss als Primzahl.
        /// </summary>
        /// <param name="upTo">Zahl X</param>
        /// <returns>die Liste der Primzahlen bis Zahl X</returns>
        private static List<UInt32> PrimeNumbersMegaOptimized(
            UInt32 upTo)
        {
            if (upTo < 2)
            {
                return (new List<UInt32>(0));
            }
            else
            {
                Boolean[] isPrime;
                List<UInt32> primes;
                Int32 capacity;

                isPrime = new Boolean[upTo + 1];
                for (UInt32 i = 2; i <= upTo; i++)
                {
                    isPrime[i] = true;
                }
                for (UInt64 i = 2; i < upTo; i++)
                {
                    if (isPrime[i])
                    {
                        for (UInt64 j = i * i; j <= upTo; j += i)
                        {
                            isPrime[j] = false;
                        }
                    }
                }
                //schon ab X = 500 fällt die Primzahlquote 
                //auf 19%, eine Kapazität von 20% ist also
                //großzügig bemessen
                capacity = (Int32)(upTo / 5);
                primes = new List<UInt32>(capacity);
                for (UInt32 i = 2; i <= upTo; i++)
                {
                    if (isPrime[i])
                    {
                        primes.Add(i);
                    }
                }
                return (primes);
            }
        }

        public static void Main(string[] args)
        {
            UInt32 number;

            number = 0;
            Console.WriteLine("{0} is prime: {1}", number
                , IsPrime(number));
            try
            {
                Console.WriteLine(PrintPrimeFactors(
                    PrimeFactorization(number)));
            }
            catch (ArgumentException)
            {
                Console.WriteLine();
            }

            number = 1;
            Console.WriteLine("{0} is prime: {1}", number
                , IsPrime(number));
            try
            {
                Console.WriteLine(PrintPrimeFactors(
                    PrimeFactorization(number)));
            }
            catch (ArgumentException)
            {
                Console.WriteLine();
            }

            for (UInt32 i = 2; i < 14; i++)
            {
                number = i;
                Console.WriteLine("{0} is prime: {1}", number
                    , IsPrime(number));
                Console.WriteLine(PrintPrimeFactors(
                    PrimeFactorization(number)));
            }

            number = 49;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 53;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 997;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 997 * 997;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 444 * 333;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 444 * 333 + 1;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            number = 444 * 333 + 3;
            Console.WriteLine("{0} is prime: {1}", number, IsPrime(number));
            Console.WriteLine(PrintPrimeFactors(PrimeFactorization(number)));

            Console.WriteLine();
            Console.WriteLine();

            //1.000.000
            MeasureCalculation(1000000, 78498);

            Console.WriteLine();
            Console.WriteLine();

            //10.000.000
            MeasureCalculation(10000000, 664579);

            Console.WriteLine();
            Console.WriteLine();

            //100.000.000
            MeasureCalculation(100000000, 5761455);

            Console.WriteLine();
            Console.WriteLine();

            ////1.000.000.000
            //MeasureCalculation(1000000000, 50847534);

            using (StreamWriter sw = new StreamWriter("primes.txt", false
                , Encoding.GetEncoding("Windows-1252")))
            {
                List<UInt32> primes;

                number = 10000;
                primes = PrimeNumbersMegaOptimized(number);
                for (UInt32 i = 2; i <= number; i++)
                {
                    StringBuilder sb;

                    sb = new StringBuilder();
                    sb.Append(String.Format("{0,10}", i));
                    sb.Append(": ");
                    sb.Append(PrintPrimeFactors(
                        PrimeFactorization(i, primes)));
                    sw.Write(sb.ToString());
                }
            }

            Console.WriteLine("Press <Enter> to exit.");
            Console.ReadLine();
        }

        private static String PrintPrimeFactors(List<UInt32> list)
        {
            StringBuilder sb;

            if (list == null)
            {
                throw (new ArgumentNullException("list"));
            }
            sb = new StringBuilder();
            for (Int32 i = 0; i < list.Count - 1; i++)
            {
                sb.Append(String.Format("{0} * ", list[i]));
            }
            sb.AppendLine(list[list.Count - 1].ToString());
            return (sb.ToString());
        }

        private static void MeasureCalculation(UInt32 upTo
            , UInt32 expectedResult)
        {
            if (upTo <= 10000000)
            {
                MeasureCalculation(PrimeNumbersStandard, upTo
                    , expectedResult);
            }
            if (upTo < 100000000)
            {
                MeasureCalculation(PrimeNumbersOptimized, upTo
                    , expectedResult);
            }
            if (upTo < 1000000000)
            {
                MeasureCalculation(PrimeNumbersSuperOptimized, upTo
                    , expectedResult);
            }
            MeasureCalculation(PrimeNumbersUltraOptimized, upTo
                , expectedResult);
            MeasureCalculation(PrimeNumbersMegaOptimized, upTo
                , expectedResult);
        }

        private static void MeasureCalculation(
            Func<UInt32, List<UInt32>> function, UInt32 upTo
            , UInt32 expectedResult)
        {
            List<UInt32> list;
            DateTime start;
            DateTime end;

            start = DateTime.Now;
            list = function(upTo);
            end = DateTime.Now;
            Console.WriteLine(list.Count);
            Debug.Assert(expectedResult == list.Count
                , "Wrong calculation!");
            Console.WriteLine((end.Subtract(start)).ToString("G"));
        }
    }
}
Abgelegt unter primzahlen.

Kommentare zum Snippet

 

Logge dich ein, um hier zu kommentieren!