using Console	= System.Console;
using DateTime	= System.DateTime;
using Debug		= System.Diagnostics.Debug;
using BitArray	= System.Collections.BitArray;
using IntList	= System.Collections.Generic.List<int>;

namespace PrimeNumberGenerator
{
	public class Generator
	{
		#region [ FindPrimes ]

		/// <summary>
		/// Returns a list of primes between 0 and max, not including max.
		/// </summary>
		/// <param name="max">The upper range value. Must be > 2.</param>
		/// <param name="elapsed">The amount of time it took to find the primes.</param>
		public static IntList FindPrimes(int max, out System.TimeSpan elapsed)
		{
			if (max < 2)
			{
				throw new System.ArgumentException(
					"Max candidates needs to be greater than 2.", "max");				
			}

			DateTime start = DateTime.Now;
			IntList primes = new IntList();
			BitArray candidates = new BitArray(max, true);

			Debug.Assert(candidates != null && candidates.Length > 0, 
				"Candidates array hasn't been initialized properly.");

			for (int i = 2; i < max; i++)
			{
				if (candidates[i] == false)
				{
					// Multiples of non-primes are also 
					// multiples of some primes, which 
					// means that we already marked them 
					// as non-primes. 
					continue;
				}

				primes.Add(i);

				for (int j = i * 2; j < max; j += i)
				{
					// Mark multiples as non-primes 
					candidates[j] = false;
				}
			}

			System.DateTime end = System.DateTime.Now;

			elapsed = end - start;

			return primes;
		}

		#endregion

		#region [ IsNumberPrime ]
		
		/// <summary>
		/// Returns true if the number is prime, false otherwise.
		/// </summary>
		public static bool IsNumberPrime(int number)
		{
			System.TimeSpan elapsed = new System.TimeSpan(0);

			IntList primes = FindPrimes(number + 1, out elapsed);

			return primes.Contains(number);
		}

		#endregion
	}
}