primes.d

module primes;


import std.range;


struct Primes(T)
{
	private
	{
		T _pos = 5;
		bool _incr = false;

		T _current = 2;
	}

	enum empty = false;

	@property T front() const
	{
		return _current;
	}

	void popFront()
	{
		if (_current == 2)
		{
			_current = 3;
		}
		else
		{
			do
			{
				_current = _pos;

				_pos += _incr ? 4 : 2;
				_incr = !_incr;
			} while (!isPrime);
		}
	}

	@property auto save()
	{
		return this;
	}

	private bool isPrime() const
	{
		assert(_current >= 5);

		if (_current % 2 == 0) return false;
		if (_current % 3 == 0) return false;

		T i = 5;
		bool incr = false;
		while (i * i <= _current)
		{
			if (_current % i == 0) return false;

			i += incr ? 4 : 2;
			incr = !incr;
		}

		return true;
	}
}

@safe pure nothrow @nogc
unittest
{
	import std.algorithm : startsWith;

	assert(Primes!uint().startsWith(only(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
		43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
		137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
		229, 233, 239, 241, 251, 257, 263, 269, 271)));
}

unittest
{
	import std.algorithm : startsWith;
	import std.bigint;

	assert(Primes!BigInt().startsWith(only(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
		43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
		137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
		229, 233, 239, 241, 251, 257, 263, 269, 271)));
}


struct TwinPrimes(T)
{
	private
	{
		Primes!T _primes;
		Tuple!(T, T) _current = Tuple!(T, T)(3, 5);
	}

	enum empty = false;

	Tuple!(T, T) front() const
	{
		return _current;
	}

	void popFront()
	{
		if (_primes.front == 2) _primes.popFrontN(2);

		T prev;
		do
		{
			prev = _primes.front;
			_primes.popFront();
		} while (prev + 2 != _primes.front);

		_current = Tuple!(T, T)(prev, _primes.front);
	}

	auto save()
	{
		return this;
	}
}

@safe pure nothrow @nogc
unittest
{
	import std.algorithm : startsWith;
	assert(TwinPrimes!ulong().map!(t => t[0]).startsWith(only(
		3, 5, 11, 17, 29, 41, 59, 71, 101, 107, 137, 149, 179, 191, 197, 227,
		239, 269, 281, 311, 347, 419, 431, 461, 521, 569, 599, 617, 641, 659,
		809, 821, 827, 857, 881, 1019, 1031, 1049, 1061, 1091, 1151, 1229, 1277,
		1289, 1301, 1319, 1427, 1451, 1481, 1487, 1607)));
}