< Summary

Information
Class: ArturRios.Util.Math.PrimeUtils
Assembly: ArturRios.Util
File(s): /home/runner/work/dotnet-util/dotnet-util/src/Math/PrimeUtils.cs
Line coverage
100%
Covered lines: 85
Uncovered lines: 0
Coverable lines: 85
Total lines: 342
Line coverage: 100%
Branch coverage
100%
Covered branches: 66
Total branches: 66
Branch coverage: 100%
Method coverage
100%
Covered methods: 14
Fully covered methods: 14
Total methods: 14
Method coverage: 100%
Full method coverage: 100%

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
IsPrimeNumber(...)100%11100%
IsPrimeNumber(...)100%11100%
IsPrimeNumber(...)100%11100%
IsPrimeNumber(...)100%11100%
IsPrimeNumber(...)100%22100%
IsPrimeNumber(...)100%1010100%
IsPrimeNumber(...)100%22100%
IsPrimeNumber(...)100%22100%
IsPrimeNumber(...)100%88100%
BigIntegerSqrt(...)100%1010100%
IsStrongProbablePrime(...)100%1616100%
RandomWitnesses()100%22100%
CheckSmallPrimesAndDivisors(...)100%1414100%

File(s)

/home/runner/work/dotnet-util/dotnet-util/src/Math/PrimeUtils.cs

#LineLine coverage
 1using System.Numerics;
 2
 3namespace ArturRios.Util.Math;
 4
 5/// <summary>
 6/// Stateless primality helpers for every built-in integer type and <see cref="BigInteger"/>.
 7/// </summary>
 8/// <remarks>
 9/// <para>
 10/// Small operands are settled by trial division. Everything that fits in 64 bits is settled by
 11/// Miller-Rabin with the witness set that is deterministic below 2^64, so the answer is exact.
 12/// Above 2^64 the test is probabilistic: see <see cref="IsPrimeNumber(BigInteger)"/>.
 13/// </para>
 14/// <para>
 15/// Every overload is pure and therefore safe to call from multiple threads. Use
 16/// <see cref="PrimeGenerator{T}"/> when a sequence of primes is needed rather than a single test.
 17/// </para>
 18/// </remarks>
 19public static class PrimeUtils
 20{
 21    /// <summary>
 22    /// Witness set that makes Miller-Rabin deterministic for every value below 2^64.
 23    /// </summary>
 124    private static readonly ulong[] DeterministicWitnesses =
 125        [2UL, 325UL, 9375UL, 28178UL, 450775UL, 9780504UL, 1795265022UL];
 26
 27    /// <summary>
 28    /// The first primes, used to strip most composites before the expensive test runs.
 29    /// </summary>
 130    private static readonly int[] SmallPrimes =
 131        [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
 32
 33    /// <summary>
 34    /// Number of random Miller-Rabin rounds applied to candidates above 2^64, where no
 35    /// deterministic witness set is known. Each round leaves at most a 1-in-4 chance of accepting a
 36    /// composite, so the overall error probability is below 4^-<see cref="ProbabilisticRounds"/>.
 37    /// </summary>
 38    private const int ProbabilisticRounds = 40;
 39
 40    /// <summary>
 41    /// Determines whether the specified 8-bit signed integer is prime.
 42    /// </summary>
 43    /// <param name="value">The value to test for primality.</param>
 44    /// <returns>True if <paramref name="value"/> is prime; otherwise false. Negative values are never prime.</returns>
 45    public static bool IsPrimeNumber(sbyte value)
 46    {
 13447        return IsPrimeNumber((int)value);
 48    }
 49
 50    /// <summary>
 51    /// Determines whether the specified 8-bit unsigned integer is prime.
 52    /// </summary>
 53    /// <param name="value">The value to test for primality.</param>
 54    /// <returns>True if <paramref name="value"/> is prime; otherwise false.</returns>
 55    public static bool IsPrimeNumber(byte value)
 56    {
 26057        return IsPrimeNumber((int)value);
 58    }
 59
 60    /// <summary>
 61    /// Determines whether the specified 16-bit signed integer is prime.
 62    /// </summary>
 63    /// <param name="value">The value to test for primality.</param>
 64    /// <returns>True if <paramref name="value"/> is prime; otherwise false. Negative values are never prime.</returns>
 65    public static bool IsPrimeNumber(short value)
 66    {
 200567        return IsPrimeNumber((int)value);
 68    }
 69
 70    /// <summary>
 71    /// Determines whether the specified 16-bit unsigned integer is prime.
 72    /// </summary>
 73    /// <param name="value">The value to test for primality.</param>
 74    /// <returns>True if <paramref name="value"/> is prime; otherwise false.</returns>
 75    public static bool IsPrimeNumber(ushort value)
 76    {
 200477        return IsPrimeNumber((int)value);
 78    }
 79
 80    /// <summary>
 81    /// Determines whether the specified 32-bit unsigned integer is prime.
 82    /// </summary>
 83    /// <param name="value">The value to test for primality.</param>
 84    /// <returns>True if <paramref name="value"/> is prime; otherwise false.</returns>
 85    public static bool IsPrimeNumber(uint value)
 86    {
 200587        return value <= int.MaxValue ? IsPrimeNumber((int)value) : IsPrimeNumber((ulong)value);
 88    }
 89
 90    /// <summary>
 91    /// Optimized primality check for 32-bit integers using trial division.
 92    /// </summary>
 93    /// <param name="value">The value to test for primality.</param>
 94    /// <returns>True if <paramref name="value"/> is prime; otherwise false. Negative values are never prime.</returns>
 95    public static bool IsPrimeNumber(int value)
 96    {
 842597        if (value < 2)
 98        {
 2499            return false;
 100        }
 101
 8401102        if (value == 2)
 103        {
 9104            return true;
 105        }
 106
 8392107        if (value % 2 == 0)
 108        {
 4186109            return false;
 110        }
 111
 4206112        var limit = (int)System.Math.Sqrt(value);
 113
 99684114        for (var divisor = 3; divisor <= limit; divisor += 2)
 115        {
 48534116            if (value % divisor == 0)
 117            {
 2898118                return false;
 119            }
 120        }
 121
 1308122        return true;
 123    }
 124
 125    /// <summary>
 126    /// Optimized primality check for 64-bit integers using deterministic Miller-Rabin for 64-bit range.
 127    /// </summary>
 128    /// <param name="value">The value to test for primality.</param>
 129    /// <returns>True if <paramref name="value"/> is prime; otherwise false. Negative values are never prime.</returns>
 130    /// <remarks>
 131    /// A negative value is rejected before the unsigned test runs. Reinterpreting its bits as a
 132    /// <see cref="ulong"/> would test a completely unrelated number: -59, for instance, would be tested
 133    /// as 2^64-59, which is prime.
 134    /// </remarks>
 135    public static bool IsPrimeNumber(long value)
 136    {
 2015137        return value >= 0L && IsPrimeNumber((ulong)value);
 138    }
 139
 140    /// <summary>
 141    /// Determines whether the specified 64-bit unsigned integer is prime.
 142    /// </summary>
 143    /// <param name="value">The value to test for primality.</param>
 144    /// <returns>True if <paramref name="value"/> is prime; otherwise false.</returns>
 145    public static bool IsPrimeNumber(ulong value)
 146    {
 6671147        var smallPrimeResult = CheckSmallPrimesAndDivisors(value);
 148
 6671149        if (smallPrimeResult.HasValue)
 150        {
 4896151            return smallPrimeResult.Value;
 152        }
 153
 9844154        return IsStrongProbablePrime(new BigInteger(value), DeterministicWitnesses.Select(witness => new BigInteger(witn
 155    }
 156
 157    /// <summary>
 158    /// Determines whether the specified <see cref="BigInteger"/> is a prime number.
 159    /// </summary>
 160    /// <param name="value">The value to test for primality.</param>
 161    /// <returns>True if <paramref name="value"/> is prime; otherwise false. Negative values are never prime.</returns>
 162    /// <remarks>
 163    /// Below 2^64 the answer is exact, because a deterministic Miller-Rabin witness set is known for that
 164    /// range. Above 2^64 the answer is probabilistic: <see cref="ProbabilisticRounds"/> random rounds are
 165    /// applied, leaving a false-positive probability below 4^-40, which is far smaller than the odds of a
 166    /// hardware fault. A "false" result is always exact. Use a certifying test such as ECPP when a proof
 167    /// rather than a very strong probability is required.
 168    /// </remarks>
 169    public static bool IsPrimeNumber(BigInteger value)
 170    {
 2016171        if (value < 2)
 172        {
 6173            return false;
 174        }
 175
 2010176        if (value <= ulong.MaxValue)
 177        {
 2004178            return IsPrimeNumber((ulong)value);
 179        }
 180
 216181        foreach (var smallPrime in SmallPrimes)
 182        {
 103183            if (value % smallPrime == 0)
 184            {
 2185                return false;
 186            }
 187        }
 188
 4189        return IsStrongProbablePrime(value, RandomWitnesses(value, ProbabilisticRounds));
 190    }
 191
 192    /// <summary>
 193    /// Computes the integer square root (floor) of the specified non-negative <see cref="BigInteger"/>.
 194    /// </summary>
 195    /// <param name="n">The non-negative value whose integer square root is to be computed.</param>
 196    /// <returns>The greatest integer less than or equal to the square root of <paramref name="n"/>.</returns>
 197    /// <exception cref="ArithmeticException"><paramref name="n"/> is negative.</exception>
 198    public static BigInteger BigIntegerSqrt(BigInteger n)
 199    {
 13200        if (n < 0)
 201        {
 1202            throw new ArithmeticException("Cannot compute square root of a negative number.");
 203        }
 204
 12205        if (n == 0)
 206        {
 1207            return 0;
 208        }
 209
 11210        BigInteger low = 1;
 211
 11212        var high = n;
 213
 96214        while (low <= high)
 215        {
 91216            var mid = (low + high) >> 1; // divide by 2
 91217            var square = mid * mid;
 91218            var compareResult = square.CompareTo(n);
 219
 91220            if (compareResult == 0)
 221            {
 6222                return mid;
 223            }
 224
 85225            if (compareResult < 0)
 226            {
 25227                low = mid + 1;
 228            }
 229            else
 230            {
 60231                high = mid - 1;
 232            }
 233        }
 234
 5235        return high;
 236    }
 237
 238    /// <summary>
 239    /// Runs the Miller-Rabin strong probable prime test against every supplied witness.
 240    /// </summary>
 241    /// <param name="value">The candidate, which must be odd and greater than the largest small prime.</param>
 242    /// <param name="witnesses">The bases to test against.</param>
 243    /// <returns>True when the candidate survives every witness.</returns>
 244    private static bool IsStrongProbablePrime(BigInteger value, IEnumerable<BigInteger> witnesses)
 245    {
 1779246        var lastValue = value - BigInteger.One;
 1779247        var d = lastValue;
 1779248        var s = 0;
 249
 5277250        while (d.IsEven)
 251        {
 3498252            d >>= 1;
 3498253            s++;
 254        }
 255
 19211256        foreach (var witness in witnesses)
 257        {
 8190258            var normalizedWitness = witness % value;
 259
 260            // A witness that is a multiple of the candidate carries no information; skip it.
 8190261            if (normalizedWitness.IsZero)
 262            {
 263                continue;
 264            }
 265
 8144266            var x = BigInteger.ModPow(normalizedWitness, d, value);
 267
 8144268            if (x.IsOne || x == lastValue)
 269            {
 270                continue;
 271            }
 272
 3144273            var roundPassed = false;
 274
 11760275            for (var iteration = 1; iteration < s; iteration++)
 276            {
 5153277                x = x * x % value;
 278
 5153279                if (x == lastValue)
 280                {
 2417281                    roundPassed = true;
 282
 2417283                    break;
 284                }
 285            }
 286
 3144287            if (!roundPassed)
 288            {
 727289                return false;
 290            }
 291        }
 292
 1052293        return true;
 727294    }
 295
 296    /// <summary>
 297    /// Produces uniformly distributed Miller-Rabin bases in the range [2, <paramref name="value"/> - 2].
 298    /// </summary>
 299    /// <param name="value">The candidate being tested.</param>
 300    /// <param name="count">How many bases to produce.</param>
 301    private static IEnumerable<BigInteger> RandomWitnesses(BigInteger value, int count)
 302    {
 303        // The candidate has already been proven larger than 2^64, so the range is never degenerate.
 4304        var range = value - 3;
 4305        var byteCount = range.GetByteCount(true);
 306
 248307        for (var i = 0; i < count; i++)
 308        {
 121309            var buffer = new byte[byteCount + 1];
 310
 121311            System.Random.Shared.NextBytes(buffer.AsSpan(0, byteCount));
 121312            buffer[byteCount] = 0; // Force a non-negative interpretation.
 313
 121314            yield return new BigInteger(buffer) % range + 2;
 315        }
 3316    }
 317
 318    /// <summary>
 319    /// Checks if a number is a small prime (2, 3, 5) or divisible by small primes.
 320    /// </summary>
 321    /// <param name="value">The value to test.</param>
 322    /// <returns>True if prime (2, 3, or 5), false if composite (divisible by 2, 3, or 5, or less than 2), null to conti
 323    private static bool? CheckSmallPrimesAndDivisors(ulong value)
 324    {
 6671325        if (value < 2UL)
 326        {
 8327            return false;
 328        }
 329
 6663330        if (value is 2UL or 3UL or 5UL)
 331        {
 51332            return true;
 333        }
 334
 6612335        if ((value & 1UL) == 0UL || value % 3UL == 0UL || value % 5UL == 0UL)
 336        {
 4837337            return false;
 338        }
 339
 1775340        return null;
 341    }
 342}
Generated by: ReportGenerator 5.5.11.0
09/08/2026 - 14:12:44
GitHub | reportgenerator.io

Methods/Properties

.cctor()
IsPrimeNumber(System.SByte)
IsPrimeNumber(System.Byte)
IsPrimeNumber(System.Int16)
IsPrimeNumber(System.UInt16)
IsPrimeNumber(System.UInt32)
IsPrimeNumber(System.Int32)
IsPrimeNumber(System.Int64)
IsPrimeNumber(System.UInt64)
IsPrimeNumber(System.Numerics.BigInteger)
BigIntegerSqrt(System.Numerics.BigInteger)
IsStrongProbablePrime(System.Numerics.BigInteger,System.Collections.Generic.IEnumerable`1<System.Numerics.BigInteger>)
RandomWitnesses()
CheckSmallPrimesAndDivisors(System.UInt64)