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"));
}
}
}