internal sealed class BoolArray32 {
			Int32[] values, mask0, mask1;

			public BoolArray32(Int32 _size)
			{
				values = new Int32[(_size - 1) / 32 + 1];

				mask1 = new Int32[32];
				mask0 = new Int32[32];
				for (int i = 0; i < 32; i++)
				{
					mask1[i] = (1 << i);
					mask0[i] = ~mask1[i];
				}
			}

			public bool this[int index] {
				get {return Get(index); }
				set {Set(index,value); }
			}

			public bool Get(int _index)
			{
				return 0 != (values[_index >> 5] & mask1[_index & 31]);
			}

			public void Set(int _index, bool _value)
			{
				int valuesIndex = _index >> 5;

				if (_value)
					values[valuesIndex] |= mask1[_index & 31];
				else
					values[valuesIndex] &= mask0[_index & 31];
			}
	    }

		static Int64 Eratosfen(Int32 len) {
			Console.Write("Test " + len);
			var sw = Stopwatch.StartNew();
			Int64 sum = 0;
// закаментить ненужное
			//var s = new bool[len];
			var s = new BoolArray32(len);
			s[0] = true;
			s[1] = true;
			Int32 found = 0;
			while(found < len) {
				sum += found;
				while(found < len && s[found]) found++; // Следующее простое
				for(Int32 i = found; i < len; i += found) s[i] = true;
			}
			Console.WriteLine(" result " + sum + " Time " + sw.ElapsedMilliseconds + " ms");

			return sum;
		}

		static void Main(string[] args) {
			Eratosfen(1000000);
			Eratosfen(2000000);
			Eratosfen(4000000);
			Eratosfen(8000000);
			Eratosfen(10000000);
			Eratosfen(20000000);
			Eratosfen(40000000);
			Eratosfen(80000000);
			Eratosfen(100000000);
			Eratosfen(200000000);
			Eratosfen(400000000);
			Eratosfen(800000000);
			return;
		}

		internal sealed class BoolArray32 {
			Int32[] values, mask0, mask1;
			Object _lock = new object();

			public BoolArray32(Int32 _size)
			{
				values = new Int32[(_size - 1) / 32 + 1];

				mask1 = new Int32[32];
				mask0 = new Int32[32];
				for (int i = 0; i < 32; i++)
				{
					mask1[i] = (1 << i);
					mask0[i] = ~mask1[i];
				}
			}

			public bool this[int index] {
				get {return Get(index); }
				set {Set(index,value); }
			}

			public bool Get(int _index)
			{
				return 0 != (values[_index >> 5] & mask1[_index & 31]);
			}

			public void Set(int _index, bool _value)
			{
				if (_value)
					values[_index >> 5] |= mask1[_index & 31];
				else
					values[_index >> 5] &= mask0[_index & 31];
			}

			public void SetInterlocked(int _index, bool _value) {
				Int32 cur, val;
				do {
					cur = values[_index >> 5];
					if (_value) {
						val = cur | mask1[_index & 31];
					} else {
						val = cur & mask0[_index & 31];
					}
				} while (cur != val && cur != Interlocked.CompareExchange(ref values[_index >> 5], val, cur));
			}

			public void SetLock(int _index, bool _value) {
				if(Get(_index) == _value) return;
				lock(_lock) {
					if (_value)
						values[_index >> 5] |= mask1[_index & 31];
					else
						values[_index >> 5] &= mask0[_index & 31];
				}
			}


		}

		static Int64 Eratosfen(Int32 len) {
			GC.Collect();
			Console.Write("Test " + len);
			var sw = Stopwatch.StartNew();
			Int64 sum = 0;
			var s = new BoolArray32(len);
			s.Set(0, true);
			s.Set(1, true);
			Int32 found = 0;
			while(found < len) {
				sum += found;
				while(found < len && s[found]) found++; // Следующее простое
				for(Int32 i = found; i < len; i += found) s.Set(i, true);
			}
			Console.WriteLine(" result " + sum + " Time " + sw.ElapsedMilliseconds + " ms");
			return sum;
		}

		static Int64 EratosfenLock(Int32 len) {
			GC.Collect();
			Console.Write("Test Lock " + len);
			var sw = Stopwatch.StartNew();
			Int64 sum = 0;
			var s = new BoolArray32(len);
			s.SetLock(0, true);
			s.SetLock(1, true);
			Int32 found = 0;
			while(found < len) {
				sum += found;
				while(found < len && s[found]) found++; // Следующее простое
				for(Int32 i = found; i < len; i += found) s.SetLock(i, true);
			}
			Console.WriteLine(" result " + sum + " Time " + sw.ElapsedMilliseconds + " ms");
			return sum;
		}

		static Int64 EratosfenInterlocked(Int32 len) {
			GC.Collect();
			Console.Write("Test Interlocked " + len);
			var sw = Stopwatch.StartNew();
			Int64 sum = 0;
			var s = new BoolArray32(len);
			s.SetInterlocked(0, true);
			s.SetInterlocked(1, true);
			Int32 found = 0;
			while(found < len) {
				sum += found;
				while(found < len && s[found]) found++; // Следующее простое
				for(Int32 i = found; i < len; i += found) s.SetInterlocked(i, true);
			}
			Console.WriteLine(" result " + sum + " Time " + sw.ElapsedMilliseconds + " ms");

			return sum;
		}

		static void Main(string[] args) {
			Eratosfen(1000000);
			EratosfenInterlocked(1000000);
			EratosfenLock(1000000);
			Eratosfen(2000000);
			EratosfenInterlocked(2000000);
			EratosfenLock(2000000);
			Eratosfen(4000000);
			EratosfenInterlocked(4000000);
			EratosfenLock(4000000);
			Eratosfen(8000000);
			EratosfenInterlocked(8000000);
			EratosfenLock(8000000);
			return;
}