Eine statische Klasse, die zahlreiche nützliche Methoden zum Rechnen mit natürlichen Zahlen bereitstellt, wie zum Beispiel ggT (=GCD), kgV (=SCM), Faktorisation, Teilerliste sowie Umwandlung in römische Zahlen und zurück.
Benötigt Snippet PrimeNumberReader
/// <summary>
/// A static class providing useful methods for integer calculations
/// </summary>
public static class Integers
{
/// <summary>
/// Calculates the Greatest Common Dividor of two integer
/// </summary>
/// <param name="Number1">the first integer</param>
/// <param name="Number2">the second integer</param>
/// <returns>the Greatest Common Dividor</returns>
public static long GetGCD(long Number1, long Number2)
{
long remainder = 0;
do
{
remainder = Number1 % Number2;
Number1 = Number2;
Number2 = remainder;
} while (remainder != 0);
return Number1;
}
/// <summary>
/// Calculates the Smallest Common Multiple
/// </summary>
/// <param name="Number1">the first integer</param>
/// <param name="Number2">the first integer</param>
/// <returns>the Smallest Common Multiple</returns>
public static long GetSCM(long Number1, long Number2)
{
return (Number1 * Number2) / GetGCD(Number1, Number2);
}
/// <summary>
/// Checks if an integer divides another
/// </summary>
/// <param name="Number1">the Divident</param>
/// <param name="Number2">the Dividor</param>
/// <returns>true if Number2 ist dividor of Number1, else false</returns>
public static bool IsDivider(long Number1, long Number2)
{
return (Number1 % Number2) == 0;
}
/// <summary>
/// test if an integer is prime
/// </summary>
/// <param name="Number">the integer</param>
/// <returns>true if prime else false</returns>
public static bool IsPrime(long Number)
{
bool value;
PrimeNumberReader pnreader = new PrimeNumberReader();
pnreader.BeginGetNextPrime();
if (pnreader.GetNextPrime(Number - 1) == Number)
{
value = true;
}
else
{
value = false;
}
pnreader.EndGetNextPrime();
return value;
}
/// <summary>
/// Converts an integer to a string containing a roman number
/// </summary>
/// <param name="Number">The integer</param>
/// <returns>The string containing the roman</returns>
public static string ToRoman(long Number)
{
if (Number == 0)
{
return string.Empty;
}
if (Number >= 1000)
{
return "M" + ToRoman(Number - 1000);
}
if (Number >= 900)
{
return "CM" + ToRoman(Number - 900);
}
if (Number >= 500)
{
return "D" + ToRoman(Number - 500);
}
if (Number >= 400)
{
return "CD" + ToRoman(Number - 400);
}
if (Number >= 100)
{
return "C" + ToRoman(Number - 100);
}
if (Number >= 90)
{
return "XC" + ToRoman(Number - 90);
}
if (Number >= 50)
{
return "L" + ToRoman(Number - 50);
}
if (Number >= 40)
{
return "XL" + ToRoman(Number - 40);
}
if (Number >= 10)
{
return "X" + ToRoman(Number - 10);
}
if (Number >= 9)
{
return "IX" + ToRoman(Number - 9);
}
if (Number >= 5)
{
return "V" + ToRoman(Number - 5);
}
if (Number >= 4)
{
return "IV" + ToRoman(Number - 4);
}
if (Number >= 1)
{
return "I" + ToRoman(Number - 1);
}
return string.Empty;
}
/// <summary>
/// Converts a string containing a roman number to an integer
/// </summary>
/// <param name="Roman">The string containing a roman number</param>
/// <returns>The integer</returns>
public static long FromRoman(string Roman)
{
if (Roman.Length == 0)
{
return 0;
}
Roman = Roman.ToUpper();
long intern = 0;
for (int i = 0; i < Roman.Length; i++)
{
int value = 0;
switch (Roman[i])
{
case 'M':
value = +1000;
break;
case 'D':
value = +500;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("M").IndexOf(Roman[j]) != -1)
{
value = -500;
break;
}
}
break;
case 'C':
value = +100;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("MD").IndexOf(Roman[j]) != -1)
{
value = -100;
break;
}
}
break;
case 'L':
value = +50;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("MDC").IndexOf(Roman[j]) != -1)
{
value = -50;
break;
}
}
break;
case 'X':
value = +10;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("MDCL").IndexOf(Roman[j]) != -1)
{
value = -10;
break;
}
}
break;
case 'V':
value = +5;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("MDCLX").IndexOf(Roman[j]) != -1)
{
value = -5;
break;
}
}
break;
case 'I':
value = +1;
for (int j = i + 1; j < Roman.Length; j++)
{
if (("MDCLXV").IndexOf(Roman[j]) != -1)
{
value = -1;
break;
}
}
break;
default:
throw new ArgumentException("Roman number string contains an illegal character at index " + i.ToString());
}
intern += Convert.ToInt64(value);
}
return Convert.ToInt64( intern );
}
/// <summary>
/// Calculates the prime number factorization of a given integer
/// </summary>
/// <param name="Number">The integer to be factorized</param>
/// <returns>A SortedDictionary where the keys are the prime factors and the corresponding values their exponent</returns>
public static SortedDictionary<long,long> GetPrimeFactorization(long Number)
{
if (Number == 0)
{
throw new ArgumentOutOfRangeException("Number", "parameter must be greater than zero");
}
SortedDictionary<long, long> factors = new SortedDictionary<long, long>();
if (Number == 1)
{
factors.Add(1, 1);
return factors;
}
long MaxFactor = Convert.ToInt64(Math.Ceiling(Math.Sqrt(Number)));
long CurrentPrime;
PrimeNumberReader pnr = new PrimeNumberReader();
pnr.BeginGetNextPrime();
do
{
CurrentPrime = pnr.GetNextPrime();
while ((Number % CurrentPrime) == 0)
{
Number /= CurrentPrime;
if (factors.ContainsKey(CurrentPrime))
{
factors[CurrentPrime]++;
}
else
{
factors.Add(CurrentPrime, 1);
}
}
if (Number == 1)
{
break;
}
}
while (MaxFactor > CurrentPrime);
if (Number != 1)
{
if (factors.ContainsKey(Number))
{
factors[Number]++;
}
else
{
factors.Add(Number, 1);
}
}
pnr.EndGetNextPrime();
return factors;
}
/// <summary>
/// Generates a list containing all the dividers of a given integer
/// </summary>
/// <param name="Number">The integer</param>
/// <returns>A List containing the dividers</returns>
public static List<long> GetDividers(long Number)
{
return Integers.GetDividers(GetPrimeFactorization(Number));
}
/// <summary>
/// Generates a list containing all the dividers of an integer specified by its prime factorization
/// </summary>
/// <param name="PrimeFactorization">The prime factorization of the integer</param>
/// <returns>A List containing the dividers</returns>
public static List<long> GetDividers(SortedDictionary<long,long> PrimeFactorization)
{
SortedDictionary<long, long> DividerMask = new SortedDictionary<long, long>();
long DividerCount = 1;
foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
{
DividerCount *= pfactor.Value + 1;
long divMask = 1;
foreach (KeyValuePair<long, long> dmask in DividerMask)
{
divMask *= PrimeFactorization[dmask.Key] + 1;
}
DividerMask.Add(pfactor.Key, divMask);
}
List<long> Dividers = new List<long>(Convert.ToInt32(DividerCount));
for (long i = 0; i < DividerCount; i++)
{
long Divider = 1;
foreach (KeyValuePair<long, long> pfactor in PrimeFactorization)
{
long pow = (i / DividerMask[pfactor.Key]) % (pfactor.Value + 1);
for (long j = 1; j <= pow; j++)
{
Divider *= pfactor.Key;
}
}
Dividers.Add(Divider);
}
Dividers.Sort();
return Dividers;
}
}
Abgelegt unter
römisch,
roman,
zahl,
zahlen,
number,
integer,
prim,
primzahl,
primfaktor,
prime,
factor,
teiler,
divider,
faktorisation,
zerlegung,
facorization,
.
Kommentare zum Snippet