ctprimes source code

1 /**
2     This module provides arrays of prime numbers that are available at compile-time.
3     Arrays are calculated as long as you need, using CTFE.
4 
5     This module uses the Sieve of Eratosthenes to find primes and so is
6     reasonably performant, but care should be taken with memory usage. For
7     example, with dmd without -lowmem, an array of only 26k primes will cost 3
8     GB of memory during compilation.
9 */
10 module ctprimes;
11 
12 import std.traits : isIntegral;
13 
14 pure size_t nth_prime_upper_bound(size_t n)
15 {
16     import std.math : log;
17 
18     if (n > 6)
19         return cast(size_t)(n * log(n) + n * log(log(n)));
20     else
21         return 11;
22 }
23 
24 pure bool[] composites(size_t length)
25 {
26     bool[] sieve; // false = prime. ignore indexes < 2
27     sieve.length = length;
28     foreach (i; 2 .. length)
29     {
30         if (!sieve[i])
31         {
32             size_t j = i + i;
33             while (j < length)
34             {
35                 sieve[j] = true;
36                 j += i;
37             }
38         }
39     }
40     return sieve;
41 }
42 
43 /**
44     Construct an array of prime number using CTFE.
45     The length of the array is `length`, and the type is `T[length]`.
46 
47     Params:
48         length = Length of array
49         T = The type of the elements of the array
50 */
51 public template ctPrimes(size_t length, T = size_t) if (isIntegral!T && 0 < length)
52 {
53     enum T[length] ctPrimes = () {
54         T[] result;
55         result.reserve(length);
56         auto sieve = composites(nth_prime_upper_bound(length));
57         foreach (i; 2 .. sieve.length)
58         {
59             if (!sieve[i])
60                 result ~= cast(T) i;
61         }
62         result.length = length;
63         return result;
64     }();
65 }
66 
67 ///
68 @safe unittest
69 {
70     import std.random : uniform;
71 
72     auto runtimevalue = uniform(0, 5);
73     static assert(!__traits(compiles, {
74             ctPrimes!runtimevalue; // Error: variable runtimevalue cannot be read at compile time
75         }));
76 
77     static assert(__traits(compiles, {
78             auto a = ctPrimes!(5, byte);
79             auto b = ctPrimes!(5, ubyte);
80             auto c = ctPrimes!(5, short);
81             auto d = ctPrimes!(5, int);
82             auto e = ctPrimes!(5, long);
83         }));
84 
85     static assert(!__traits(compiles, {
86             auto a = ctPrimes!(5, bool);
87             auto b = ctPrimes!(5, char);
88             auto c = ctPrimes!(5, double);
89         }));
90 
91     auto primes1 = ctPrimes!(10);
92     static assert(is(typeof(primes1) == size_t[10]));
93     assert(primes1 == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
94 
95     auto primes2 = ctPrimes!(1);
96     assert(primes2 == [2]);
97 
98     auto primes3 = ctPrimes!(10_000);
99     assert(primes3[$ - 1] == 104_729);
100 }
101 
102 /**
103     Construct an array of all prime numbers less than N, using CTFE.
104     The type of the array is `typeof(N)[]`.
105 
106     Params:
107         N = All elements of result are less than this value
108 */
109 public template ctPrimesLessThan(alias N) if (isIntegral!(typeof(N)))
110 {
111     enum typeof(N)[] ctPrimesLessThan = () {
112         typeof(N)[] result;
113         result.reserve(N);
114         auto sieve = composites(N);
115         foreach (i; 2 .. sieve.length)
116         {
117             if (!sieve[i])
118                 result ~= cast(typeof(N)) i;
119         }
120         return result;
121     }();
122 }
123 
124 @safe unittest
125 {
126     import std.random : uniform;
127 
128     auto runtimevalue = uniform(0, 5);
129     static assert(!__traits(compiles, {
130             ctPrimes!runtimevalue; // Error: variable runtimevalue cannot be read at compile time
131         }));
132 
133     static assert(__traits(compiles, {
134             auto a = ctPrimesLessThan!(cast(byte) 5);
135             auto b = ctPrimesLessThan!(cast(ubyte) 5);
136             auto c = ctPrimesLessThan!(cast(short) 5);
137             auto d = ctPrimesLessThan!(cast(int) 5);
138             auto e = ctPrimesLessThan!(cast(long) 5);
139         }));
140 
141     static assert(!__traits(compiles, {
142             auto a = ctPrimesLessThan!(true);
143             auto b = ctPrimesLessThan!('a');
144             auto c = ctPrimesLessThan!(5f);
145         }));
146 
147     auto primes1 = ctPrimesLessThan!(10);
148     static assert(is(typeof(primes1) == typeof([1])));
149     assert(primes1 == [2, 3, 5, 7]);
150 
151     auto primes2 = ctPrimesLessThan!(2);
152     assert(primes2 == []);
153 
154     auto primes3 = ctPrimesLessThan!(0);
155     assert(primes3 == []);
156 
157     auto primes4 = ctPrimesLessThan!(104_730);
158     assert(primes4[$ - 1] == 104_729);
159 }