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.
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!