Prime number generation refactored to IOSP/PoMO

primegenerator.cs

using System;
using System.Collections.Generic;

namespace GeneratePrimes.FlowDesign
{
	public class PrimeGenerator
	{
		const int SMALLEST_POSSIBLE_PRIME = 2;


		public static int[] GeneratePrimeNumbers(int maxValue)
		{
			var prime_candidates = Initialize_prime_candidates (maxValue);
			Cross_out_multiples (prime_candidates);
			return Extract_primes_from_candidates (prime_candidates);
		}


		static void Cross_out_multiples(bool[] prime_candidates) {
			var limit = Calculate_upper_limit_for_candidates (prime_candidates);
			Enumerate_still_valid_prime_candidates (prime_candidates, limit,
				i => Cross_out_multiples_of (i, prime_candidates));
		}

		static int Calculate_upper_limit_for_candidates(bool[] prime_candidates) {
			return (int)Math.Sqrt(prime_candidates.Length);
		}

		static void Enumerate_still_valid_prime_candidates(bool[] prime_candidates, int upper_limit, Action<int> onValid) {
			for (var i = SMALLEST_POSSIBLE_PRIME; i <= upper_limit; i++)
				if (prime_candidates [i])
					onValid (i);
		}

		static void Cross_out_multiples_of(int i, bool[] prime_candidates) {
			for (int multiple = 2 * i; multiple < prime_candidates.Length; multiple += i)
				prime_candidates[multiple] = false;
		}



		static bool[] Initialize_prime_candidates(int maxValue) {
			var candidates = new bool[maxValue + 1];
			for (var i = 0; i < candidates.Length; i++)
				candidates [i] = true;
			return candidates;
		}
			
		static int[] Extract_primes_from_candidates (bool[] prime_candidates)
		{
			var primes = new List<int> ();
			for (var i = SMALLEST_POSSIBLE_PRIME; i < prime_candidates.Length; i++)
				if (prime_candidates [i])
					primes.Add (i);
			return primes.ToArray ();
		}
	}
}

primegenerator_with_ADT.cs

using System;
using System.Collections.Generic;

namespace GeneratePrimes.FlowDesign
{
	public class PrimeGenerator
	{
		public static int[] GeneratePrimeNumbers(int maxValue)
		{
			var primeCandidates = new Primecandidates (maxValue);
			Cross_out_multiples (primeCandidates);
			return primeCandidates.Primes;
		}
			
		static void Cross_out_multiples(Primecandidates primeCandidates) {
			var limit = Calculate_upper_limit_for_candidates (primeCandidates);
			primeCandidates.EnumerateStillValidCandidates(limit,
				i => Cross_out_multiples_of (i, primeCandidates));
		}

		static int Calculate_upper_limit_for_candidates(Primecandidates primeCandidates) {
			return (int)Math.Sqrt(primeCandidates.Length);
		}

		static void Cross_out_multiples_of(int i, Primecandidates primeCandidates) {
			for (int multiple = 2 * i; multiple < primeCandidates.Length; multiple += i)
				primeCandidates.CrossOff(multiple);
		}
	}


	class Primecandidates {
		const int SMALLEST_POSSIBLE_PRIME = 2;

		bool[] candidates;


		public Primecandidates(int maxValue) {
			this.candidates = new bool[maxValue + 1];
			for (var i = 0; i < this.candidates.Length; i++)
				this.candidates [i] = true;
		}
			

		public void EnumerateStillValidCandidates(int max, Action<int> onValid) {
			for (var i = SMALLEST_POSSIBLE_PRIME; i <= max; i++)
				if (this.candidates [i])
					onValid (i);
		}

		public void CrossOff(int index) {
			this.candidates [index] = false;
		}

		public int Length { get { return this.candidates.Length; } }


		public int[] Primes
		{
			get {
				var primes = new List<int> ();
				for (var i = SMALLEST_POSSIBLE_PRIME; i < this.candidates.Length; i++)
					if (this.candidates [i])
						primes.Add (i);
				return primes.ToArray ();
			}
		}
	}
}

test_primegenerator.cs

// adapted from: https://gist.github.com/battermann/b2939d88d00746cea653#file-primegeneratortests-cs

using NUnit.Framework;

namespace GeneratePrimes.FlowDesign
{
	[TestFixture]
	public class test_PrimeGenerator
	{
		[Test]
		public void TestPrimes()
		{
			int[] nullArray = PrimeGenerator.GeneratePrimeNumbers(0);
			Assert.AreEqual(nullArray.Length, 0);

			int[] minArray = PrimeGenerator.GeneratePrimeNumbers(1);
			Assert.AreEqual(minArray.Length, 0);

			minArray = PrimeGenerator.GeneratePrimeNumbers(2);
			Assert.AreEqual(minArray.Length, 1);
			Assert.AreEqual(minArray[0], 2);

			int[] threeArray = PrimeGenerator.GeneratePrimeNumbers(3);
			Assert.AreEqual(threeArray.Length, 2);
			Assert.AreEqual(threeArray[0], 2);
			Assert.AreEqual(threeArray[1], 3);

			int[] centArray = PrimeGenerator.GeneratePrimeNumbers(100);
			Assert.AreEqual(centArray.Length, 25);
			Assert.AreEqual(centArray[24], 97);
		}

		[Test]
		public void TestExhaustive()
		{
			for (int i = 2; i < 500; i++)
				VerifyPrimeList(PrimeGenerator.GeneratePrimeNumbers(i));
		}

		private void VerifyPrimeList(int[] list)
		{
			for (int i = 0; i < list.Length; i++)
				VerifyPrime(list[i]);
		}

		private void VerifyPrime(int n)
		{
			for (int factor = 2; factor < n; factor++)
				Assert.IsTrue(n % factor != 0);
		}
	}
}