| | | 1 | | using System.Numerics; |
| | | 2 | | |
| | | 3 | | namespace ArturRios.Util.Math; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A generic prime number generator that yields the primes of an integer type in ascending order. |
| | | 7 | | /// Create an instance to get an independent sequence of primes. |
| | | 8 | | /// </summary> |
| | | 9 | | /// <typeparam name="T"> |
| | | 10 | | /// The integer type to generate primes for. Any <see cref="IBinaryInteger{TSelf}"/> works, which covers |
| | | 11 | | /// sbyte, byte, short, ushort, int, uint, long, ulong, nint, nuint, Int128, UInt128 and |
| | | 12 | | /// <see cref="BigInteger"/>. Types that cannot represent integers, such as double or decimal, are |
| | | 13 | | /// rejected by the compiler rather than at run time. |
| | | 14 | | /// </typeparam> |
| | | 15 | | public class PrimeGenerator<T> where T : IBinaryInteger<T> |
| | | 16 | | { |
| | 14 | 17 | | private readonly Lock _lock = new(); |
| | 14 | 18 | | private T _current = T.One; |
| | | 19 | | |
| | | 20 | | /// <summary> |
| | | 21 | | /// Returns the next prime in the sequence (2, 3, 5, 7, ...). |
| | | 22 | | /// Thread-safe. |
| | | 23 | | /// </summary> |
| | | 24 | | /// <returns>The next prime number of type T.</returns> |
| | | 25 | | /// <exception cref="OverflowException"> |
| | | 26 | | /// Thrown when the sequence runs past the largest prime representable by <typeparamref name="T"/>. |
| | | 27 | | /// The generator is left on its last prime, so a subsequent call throws again rather than wrapping. |
| | | 28 | | /// </exception> |
| | | 29 | | public T Next() |
| | 182 | 30 | | { |
| | | 31 | | lock (_lock) |
| | | 32 | | { |
| | 182 | 33 | | var two = T.One + T.One; |
| | 182 | 34 | | var candidate = Increment(_current); |
| | | 35 | | |
| | 179 | 36 | | if (candidate < two) |
| | | 37 | | { |
| | 0 | 38 | | candidate = two; |
| | | 39 | | } |
| | | 40 | | |
| | 649 | 41 | | while (!IsPrime(candidate)) |
| | | 42 | | { |
| | 471 | 43 | | candidate = Increment(candidate); |
| | | 44 | | } |
| | | 45 | | |
| | 178 | 46 | | _current = candidate; |
| | | 47 | | |
| | 178 | 48 | | return candidate; |
| | | 49 | | } |
| | 178 | 50 | | } |
| | | 51 | | |
| | | 52 | | /// <summary> |
| | | 53 | | /// Adds one, surfacing an <see cref="OverflowException"/> instead of wrapping around. |
| | | 54 | | /// </summary> |
| | | 55 | | /// <remarks> |
| | | 56 | | /// The checked operator is a no-op for <see cref="BigInteger"/>, which never overflows, and throws for |
| | | 57 | | /// every fixed-width type. |
| | | 58 | | /// </remarks> |
| | 653 | 59 | | private static T Increment(T value) => checked(value + T.One); |
| | | 60 | | |
| | | 61 | | /// <summary> |
| | | 62 | | /// Tests a candidate using the narrowest <see cref="PrimeUtils"/> overload that can hold it. |
| | | 63 | | /// </summary> |
| | | 64 | | private static bool IsPrime(T candidate) |
| | | 65 | | { |
| | 649 | 66 | | if (T.IsNegative(candidate)) |
| | | 67 | | { |
| | 0 | 68 | | return false; |
| | | 69 | | } |
| | | 70 | | |
| | | 71 | | // A non-negative value of eight bytes or fewer always fits in a ulong, sign bit included. |
| | 649 | 72 | | return candidate.GetByteCount() <= sizeof(ulong) |
| | 649 | 73 | | ? PrimeUtils.IsPrimeNumber(ulong.CreateTruncating(candidate)) |
| | 649 | 74 | | : PrimeUtils.IsPrimeNumber(BigInteger.CreateChecked(candidate)); |
| | | 75 | | } |
| | | 76 | | } |