This very fast, simple sieve quickly finds 31 bit primes. It uses a memory efficient BitArray for odd numbers.
How a 32 bit int is a 31 bit prime
Since a prime number must be > 1, the sign bit has no bearing, leaving 31 bits to store the positive numbers. This differs from uint which truly would be 32 bit primes.
See this Microsoft link on Magic Numbers.
If you find the value 2147483647 on that page you will see this text:
The maximum signed 32 bit value. Largest 31 bit prime.
On an unrelated note, the Magic Numbers link has some pretty interesting things in it.
public static class Sieve31
{
public static IEnumerable<int> Primes(int upperLimit)
{
if (upperLimit < 2)
{
throw new ArgumentException("Upper Limit be must greater than or equal to 2.");
}
yield return 2;
if (upperLimit == 2)
{
yield break;
}
// Check odd numbers for primality
const int offset = 3;
Func<int, int> ToNumber = delegate(int index) { return (2 * index) + offset; };
Func<int, int> ToIndex = delegate(int number) { return (number - offset) / 2; };
var bits = new BitArray(ToIndex(upperLimit) + 1, defaultValue: true);
var upperSqrtIndex = ToIndex((int)Math.Sqrt(upperLimit));
for (var i = 0; i <= upperSqrtIndex; i++)
{
// If this bit has already been turned off, then its associated number is composite.
if (!bits[i]) continue;
var number = ToNumber(i);
// The instant we have a known prime, immediately yield its value.
yield return number;
// Any multiples of number are composite and their respective bits should be turned off.
for (var j = ToIndex(number * number); (j > i) && (j < bits.Length); j += number)
{
bits[j] = false;
}
}
// Output remaining primes once bit array is fully resolved:
for (var i = upperSqrtIndex + 1; i < bits.Length; i++)
{
if (bits[i])
{
yield return ToNumber(i);
}
}
}
}
Example Usage
Here’s a simple example that counts the number of primes found and finds the largest one.
var count = 0;
var largest = 0;
var primes = Sieve31.Primes(int.MaxValue);
foreach (var prime in primes)
{
count++;
largest = prime;
}
Worst Case Scenario: int.MaxValue
The BitArray will have a Length of 1,073,741,823 bits, which is 128 megabytes. This will yield 105,097,565 primes.
If you want to store the primes to a List<int>, the code is quite easy:
var primeList = Sieve31.Primes(int.MaxValue).ToList();
The resulting list would require 409 megabytes, in addition to the 128 for the BitArray. On my laptop this takes about 40 seconds. Since BitArray is not thread safe, this is close to the best I can hope for on a single thread.
An indexed list is strongly recommended
When processing primes it is often, but not always, preferred to use an indexed list. Assuming, of course, that you have sufficient memory to do so. Worst case you need 530 megabytes to generate the list, and once it’s done, you get back 128 MB but now would have a fast Count and a fast index at your fingertips.
If you don’t use a list, and need to loop over the primes more than once, the BitArray is completely regenerated every time, which could degrade performance.
A Challenge Problem
Given an extremely large int upper limit, perhaps anything over 1 billion, build a random list of 100 primes. You cannot hardcode any known prime counts.
Short, Easy Solution
The easiest solution is to use the recommended indexed list, if memory allows.
private IList<int> GetRandom100Easy(int upperLimit)
{
var answer = new List<int>();
var primeList = Sieve31.Primes(upperLimit).ToList();
var random = new Random();
for (var i = 0; i < 100; i++)
{
var index = random.Next(primeList.Count);
answer.Add(primeList[index]);
}
return answer;
}
Longer, Low Memory Solution
If you don’t have sufficient memory to produce the largest possible list of primes, the solution is a lot longer and slower, as it requires two-passes over the enumerable collection. For the 2nd pass, you can exit early once the full answer is known.
private IList<int> GetRandom100LowMemory(int upperLimit)
{
// To produce this answer without a list of primes requires two-passes.
// The 2nd pass can exit early.
var primes = Sieve31.Primes(upperLimit);
// Fully loop over to get count
var primeCount = 0;
foreach (var prime in primes)
{
primeCount++;
}
// Initialize dictionary of 100 random sequences.
IDictionary<int, int> dict = new Dictionary<int, int>();
var random = new Random();
for (var i = 0; i < 100; i++)
{
dict.Add(random.Next(primeCount) + 1, 0);
}
// For early loop termination, find max sequence.
var maxSequence = dict.Keys.Max();
// Loop again to assign primes to dict.
var sequence = 0;
foreach (var prime in primes)
{
sequence++;
if (dict.ContainsKey(sequence))
{
dict[sequence] = prime;
if (sequence == maxSequence)
{
break;
}
}
}
return dict.Values.ToList();
}
As you review both solutions, I’m sure you understand why working with an indexed list is preferred.
Questions
Being this is CR, there is always an implied question of “Do you have any constructive comments?”
Are there better ways to address the challenge problem?
Listtaking up space, you can write aPrimesmethod that, instead of returning the prime numbers, just returns theBitArrayand the count. Then, you can select 100 primes from theBitArray. No need to store all the prime numbers, just the 100 \$\endgroup\$GetRandom100()uses it to generate 100 primes. But I don't see how counting could add 8 whole seconds. Instead ofyield return number, you havecount++\$\endgroup\$