Klassenvorstellung: Primzahlen

[Die erinnerung]

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

Weiters sind deine Inkrement und Dekrement Operatoren etwas eigenwillig indem sie etwas anderes als eine Kopie von bzw. Referenz auf *this zurückgeben. Würde ich ebenfalls so nicht machen.

Wie würdest du es machen? Wie ja gesagt, mir fehlt die Übung.

hustbaer schrieb:

Das statische Member storedPrimes ist problematisch was Thread-Safety angeht.

Selbe Sache.

hustbaer schrieb:

Der "is prime" Loop gehört in eine eigene Funktion. Zumindest wenn du diesen naiven Algorithmus verwendest (der alles andere als schnell ist). Dadurch sparst du dir die Hilfsvariable und das break .

Ich habe das jetzt ausgelagert. Mir ist leider kein andere Algorithmus eingefallen!

hustbaer schrieb:

Der Sinn des 2. Template-Parameters ist mir auch nicht ganz klar. Wieso sollte man wollen dass die Klasse etwas anderes als std::vector verwendet? Und unnötigerweise lass ich meinen Klassen nicht vorschreiben was sie intern zu verwenden haben.

Wer weiß. Vieleicht hat der Nutzer einen effiktiveren Container zur Verfügung, oder möchte einfach einen anderen verwenden. Macht std::vector ja genau so. (mit dem allocator)

hustbaer schrieb:

Genaugenommen ist mir sogar der Sinn des 1. Template-Parameters nicht ganz klar, da es mMn. wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist ~~ 4 Mrd. Bis 4 Mrd. gibt es so Pi * Daumen 180 Mio. Primzahlen. Bei 4 Byte pro Zahl macht das 720 MB. Das liegt schon in der Grössenordnung wo man auf 32 Bit Systemen anfängt sich Sorgen um std::bad_alloc zu machen (die 720 MB müssen ja am Stück verfügbar sein!).
Und auf 64 Bit Systemen geht dir sowieso der Speicher aus bevor size_t überläuft.

Wenn jemand z.B. eine eigene Zahlenklasse oder ähnliches hat, oder einfach einen kleineren Bereich haben will. Wer weiß.
(P.S.: Ich war selbst schon mal in solch einer Situation, in der ich eine Templateklasse hätte besser brauchen können)
(P.P.S.: Ich persönlich kenne nämlcih zwei recht spezielle Klassen. Die eine ist eine Zahlenklasse, die weit über jeden normalen Datentyp herausgeht. Die andere ist eine Containerklasse, die wenn sie zu viel RAM verbraucht gezielt auf die Festplatte auslagert. Somit kann sie deutlcih mehr als der RAM speichern.)

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

Primzahlen... Wer braucht die nicht??? (Primzahlen, fand ich halt schon immer interessant. Und ich habe mir einen kleinen Primfaktorenzerleger programmiert. Da verwende ich die Klasse)

hustbaer schrieb:

Auweh, hätte ich fast übersehen...

primzahlen[2] = 42;
std::cout << "Die 2. Primzahl ist " << primzahlen[2] << ".\n";
std::cout << "Ne, ehrlich, ist so.\n";

Habs gefixt! habe ja ganz vergessen, dass man die Refferenzen const machen muss/sollte!

P.S.: Danke für die konstruktive Kritik und die Verbesserunsgvorschläge.
Ich habe außerdem die Klasse im Startpost aktualiesiert!

[knivil]

wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist

Ich haette auch gern auf 32 Bit Systemen 64 Bit Primzahlen. Fuer einzelne verwende ich dort auch uint64_t.

Bei 4 Byte pro Zahl macht das 720 MB

Unter Verwendung von prime wheels und Bitsets kann der Speicherbedarf drastisch reduziert werden.

Tja zur Klasse ... ich mach es anders. Hierarchisch:
1.) prime_wheel - Spezifierziert das Pimzahlsieb zur Erzeugung von Primzahlen/Sieben
2.) primes - Container mit allen Primzahlen in einer bestimmten Range (echt vorhanden, Speicherbedarf O(n) )
3.) prime_sieve - Pseudocontainer fuer Primzahlen in bestimmter Range (nicht echt vorhanden, ezeugt beim Iterationsprozess, Speicherbedarf O(k), wobei k fix im Bereich des L1-Caches liegt)

Alle beiden Containertypen liefern Iteratoren um mit den Primzahlen zu arbeiten.

Btw. deine is isPrime-Funktion ist falsch. Eine gegebene Zahl kann durch Primzahlen ausserhalb deines Containers teilbar sein.

[Die erinnerung]

knivil schrieb:

Btw. deine is isPrime-Funktion ist falsch. Eine gegebene Zahl kann durch Primzahlen ausserhalb deines Containers teilbar sein.

Nicht in dem Zusammenhang, in dem ich sie aufrufe. Ich prüfe ja alle ungeraden Zahlen der Reihe nach. Also sind (wenn ich die Funktion aufrufe) alle Primzahlen, die kleiner als die Zahl sind, vorhanden.

EDIT:

Ich habe die Performance der isPrime -Funktion erhöht.

[Nathan]

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

RandomAccessIteratoren brauchen operator[].

[hustbaer]

knivil schrieb:

wenig Sinn macht etwas anderes als size_t für die Primzahlen selbst zu verwenden. Auf 32 Bit Systemen sind das 4 Byte und der Maximale Wert ist

Ich haette auch gern auf 32 Bit Systemen 64 Bit Primzahlen. Fuer einzelne verwende ich dort auch uint64_t.

Bei 4 Byte pro Zahl macht das 720 MB

Unter Verwendung von prime wheels und Bitsets kann der Speicherbedarf drastisch reduziert werden.

Ich meinte das schon im Zusammenhang mit seiner Implementierung.

[hustbaer]

Nathan schrieb:

hustbaer schrieb:

Ich finde die Mischung aus "Iterator" (operator ++, --, und "Container" (operator []) seltsam. Würde ich so nicht machen.

RandomAccessIteratoren brauchen operator[].

Die liefern aber nicht das zurück was sein operator[] zurückliefert.

[knivil]

hustbaer schrieb:

Ich meinte das schon im Zusammenhang mit seiner Implementierung.

Ja, die Antwort war auch eher dayu gedacht, um yu yeigen, wo die Reise hingehen sollte.

Ansonsten:

#include "Primes.cpp"

Bitte nenne die Datei "Primes.impl" oder "Primes.incl" oder ... . Die Endung cpp wird von den meisten IDEs automatisch als Uebersetzungseinheit betrachtet.

[hustbaer]

Die erinnerung schrieb:

Habs gefixt! habe ja ganz vergessen, dass man die Refferenzen const machen muss/sollte!

Ich würde die eher einfach by-value zurückgeben.

Die erinnerung schrieb:

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

Primzahlen... Wer braucht die nicht??? (Primzahlen, fand ich halt schon immer interessant. Und ich habe mir einen kleinen Primfaktorenzerleger programmiert. Da verwende ich die Klasse)

Ich brauch praktisch nie Primzahlen.

Und wenn doch, dann eher eine Funktion der ich eine Zahl geben kann, die mir die nächste Primzahl die >= oder <= dieser Zahl ist zurückgibt.

Aber für "gib mir die ersten N Primzahlen" hatte ich bisher noch nie bedarf. Ausgenommen bei diversen "Programmieraufgaben" wo genau das gefragt war.

[Werner Salomon]

Hallo,

Kritik hast Du ja schon reichlich geerntet, also ich finde so eine Klasse gut! Gut deshalb weil man das ganze Brimborium mit den Primzahlen hinter dieser Schnittstelle gut unterbringen kann.
Das muss ich sogar gut finden, da ich mir vor Jahren selbst so ein Ding gebaut habe

hustbaer schrieb:

Und der Sinn deiner Klasse überhaupt ist mir nicht so ganz klar. Also mir fällt jetzt kein Anwendungsfall ein wo ich die verwenden wollen würde.

liegt wohl daran, dass Du noch nie ein Problem aus projecteuler.net bearbeitet hast.

Zwei Dinge rufen dann doch nach Verbesserungsbedarf.
1.) Du kannst deutlich an Performance gewinnen, wenn Du bei der Suche nach einem möglichen Teiler nur bis <=sqrt(number) statt bis number läuft. Dies macht sich umso stärker bemerkbar, je größer die Primzahlen werden.
2.) Die Funktion zur Bestimmung ob eine Zahl eine Primzahl gehört isoliert - hast Du schon gemacht.

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen bietet es sich an, die Hilfen von boost zu nutzen. Siehe dazu den boost.iterator.adaptor.

Ich finde es gut, wenn Du Deine Klasse hier zur Diskussion stellst.
Gruß
Werner

[Die erinnerung]

Werner Salomon schrieb:

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

Könntest du etwas konkreter werden? Ich verstehe leider nciht ganz, was du meinst.

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen bietet es sich an, die Hilfen von boost zu nutzen. Siehe dazu den boost.iterator.adaptor

Das werde ich mir mal anschauen. Dennoch könnte ein wenig Hilfe nicht schaden, da ich sowas noch nie gemacht habe!

Außerdem danke für deine aufbauende Worte. Und für den Tipp mit der Wurzel. Ich hatte jetzt vorübergehend den zu überprüfenden Wert quadriert und mit der Zahl verglichen. Diese methode ist besonmders bei goßen Primzahlen deutlich effizienter. Habe ich auch in meinen Test festgestellt!

[Werner Salomon]

Die erinnerung schrieb:

Werner Salomon schrieb:

2a) statt einer Methode IsPrime würde ich hier eine freie Funktion verwenden, die intern wieder ein Objekt der Klasse Primes nutzt. So kann die Funktion auch außerhalb der Klasse einfach und ohne Angabe der Template-Parameter genutzt werden.

Könntest du etwas konkreter werden? Ich verstehe leider nciht ganz, was du meinst.

Einfach eine Funktion, in der die Klasse Prime wieder benutzt wird - also etwa so:

// --   freie Funktion 'isPrime' liefert 'true', falls x eine Primzahl ist.
template< typename T >
bool isPrime( const T& x )
{
    const T divisor_max = T(std::sqrt( double(x) )); // erfordert #include <cmath>
    for( Prime< T > i; *i <= divisor_max; ++i )
        if( x % *i == 0 )
            return false;
    return true;
}

.. und die benutzt Du dann wie gehabt in const T& Primes<T, Container>::operator[](size_t pos) . Eventuell musst Du noch einen Prototyp vor die Klasse schreiben.

Gruß
Werner

[hustbaer]

@Werner Salomon
Das meinte ich ja: ausserhalb von diversen "Übungen" hab' ich noch nie Primzahlen gebraucht. Ich meinte mal welche zu brauchen als ich für ein Projekt nen eigenen Hashtable implementieren wollte. Hat sich dann aber - wie es meist der Fall ist - herausgestellt, dass es nicht sinnvoll/nötig ist hier was selbst zu basteln.

Und sollte ich je welche brauchen, dann such ich mir ne passende Library, die dann auch entsprechend schnell ist

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen ...

Naja, ist sie eben nicht. Sie tut bloss ein bisschen ähnlich wie ein Iterator. Das war ja auch einer meiner Kritikpunkte.

Guck dir mal die Returnwerte der ++/-- Operatoren an und was der [] Operator macht...

Und Funktionen die nicht Thread-safe sind sind mir generell ein Greul. Genau so wie Funktionen die ungefragterweise mächtig Speicher verbrauchen, und diesen nach Aufruf der Funktion nicht mehr freigeben. Beides ist hier gegeben. Dummerweise hab' ich keinen Vorschlag wie man das besser machen kann, ohne gleichzeitig die Verwendung wesentlich unparktischer zu machen...

[Werner Salomon]

hustbaer schrieb:

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen ...

Naja, ist sie eben nicht. Sie tut bloss ein bisschen ähnlich wie ein Iterator. Das war ja auch einer meiner Kritikpunkte.

Guck dir mal die Returnwerte der ++/-- Operatoren an und was der [] Operator macht...

Ja - ich bin absolut Deiner Meinung. Habe mich bloss falsch ausgedrückt.
So eine Klasse wie Prime ist vom Konzept her ein Iterator und sollte sich natürlich auch so verhalten, dass heißt z.B. im operator++ ein return *this; und kein Value.

hustbaer schrieb:

Und Funktionen die nicht Thread-safe sind sind mir generell ein Greul.

Thread-Safety ist im Kontext der Probleme aus Projecteuler i.A. schlicht überflüssig, und man könnte es relativ leicht hinzufügen.

Gruß
Werner

[Die erinnerung]

Werner Salomon schrieb:

template< typename T >
bool isPrime( const T& x )
{
    const T divisor_max = T(std::sqrt( double(x) )); // erfordert #include <cmath>
    for( Prime< T > i; *i <= divisor_max; ++i )
        if( x % *i == 0 )
            return false;
    return true;
}

Ich finde die Idee echt genial. Ich habe sie in einer leicht modifizierten Version umgestzt!

Wegen der Iteratordiskussion:

Ich habe keinerlei Problem, bei den inkrementen und Dekrementen this zurückzugeben. Werde ich dann auch noch umsetzten.

Zum Thema Threadsicherheit: Wie genau mache ich das?

[hustbaer]

Werner Salomon schrieb:

hustbaer schrieb:

Und Funktionen die nicht Thread-safe sind sind mir generell ein Greul.

Thread-Safety ist im Kontext der Probleme aus Projecteuler i.A. schlicht überflüssig, und man könnte es relativ leicht hinzufügen.

OK.
Kommt halt drauf an was man haben will. Wenn man "nur" ein nettes Werkzeug für solcherlei Aufgaben will, dann OK.

Andrerseits kann man bei den Projecteuler Aufgaben vermutlich auch gut damit leben irgendwo ne globale Instanz einer Klasse zu haben. Statt freie Funktionen würde man dann einfach Memberfunktionen dieser Klasse aufrufen. Und die Klasse könnte man dann leicht Thread-safe machen (im Sinn von "verschiedene Instanzen in verschiedenen Threads = OK, selbe Instanz in verschiedenen Threads = nicht OK" -- die "üblichen Regeln" halt).

[hustbaer]

Die erinnerung schrieb:

Zum Thema Threadsicherheit: Wie genau mache ich das?

Die einfachste Variante wäre in jeder Funktion die auf deine statische Membervariable zugreift eine (ebenso statische) Mutex zu locken.
Dummerweise kostet das auch einiges an Performance. So ein Mutex Lock + Unlock ist nicht ganz billig.
Im Vergleich dazu zig oder hunderte Primzahlen-Kandidaten durchzuspulen ist es vermutlich sehr billig.
Im Vergleich dazu einfach nur in einen Vektor reinzugreifen und eine Zahl daraus zurückzugeben ist es vermutlich eher nicht so billig.

[volkard]

Werner Salomon schrieb:

Thread-Safety ist im Kontext der Probleme aus Projecteuler i.A. schlicht überflüssig, und man könnte es relativ leicht hinzufügen.

Autsch. Fürs ProjektEuler brauchste normalerweise auch keinen Cache der Primzahlen. Und falls doch, füllt man sich einfach vorher einen vector damit.

Den Generator wie Iteratoren aussehen zu lassen, naja...
Da liegt auch das Problem mit der Thread-Safety.

Dein Vorschlag, die IsPrime auszulagern, ach nöö, so aber nicht. Soll schon, wenn man schon alle Primzahlen speichern will, die Speicherung auch benutzen dürfen.

[volkard]

Die erinnerung schrieb:

Werner Salomon schrieb:

template< typename T >
bool isPrime( const T& x )
{
    const T divisor_max = T(std::sqrt( double(x) )); // erfordert #include <cmath>
    for( Prime< T > i; *i <= divisor_max; ++i )
        if( x % *i == 0 )
            return false;
    return true;
}

Ich finde die Idee echt genial. Ich habe sie in einer leicht modifizierten Version umgestzt!

Aber wenn Du uns nicht auf dem Laufenden hältst, werden wir bald schrecklich aneinander vorbeireden.
Wenn Du DIESE Version benutzt hast, wozu dann überhaupt noch die Primzahlen speichern? Weder Dein Primfaktorenprogramm noch die anderen Übungen brauchen, daß Du im Primzahlenfeld vorwärts und rückwärts laufen kannst, oder?

[Werner Salomon]

Die erinnerung schrieb:

Werner Salomon schrieb:

Bleibt noch zu erwähnen, dass aus der Sicht von C++ und der STL die Klasse Primes ein Iterator ist. Also sollte man es zu einen auch so benenne und zum anderen bietet es sich an, die Hilfen von boost zu nutzen. Siehe dazu den boost.iterator.adaptor

Das werde ich mir mal anschauen. Dennoch könnte ein wenig Hilfe nicht schaden, da ich sowas noch nie gemacht habe!

Ich habe Dir mal einen Iterator für (Pseudo-)Primzahlen gebastelt. Du musst nur noch die Methode dereference() für die Primzahl-Bestimmung erweitern. Die Methode base() liefert Dir den Index auf den Container storedPrimes .

#include <boost/iterator/iterator_adaptor.hpp>

template< typename T >
class Primes : public boost::iterator_adaptor< Primes< T >, 
    std::size_t,    // gibt den unterliegenden Typ an, wird inkrementiert, dekrementiert und mit offset addiert/subtrahiert
    T,              // value_type des Iterators
    std::random_access_iterator_tag, // Ja - ist tatsächlich random-access; braucht man nicht, kriegt man aber geschenkt
    const T,        // Referenz-Typ; const ist wichtig, damit ist es ein const_iterator
    std::ptrdiff_t  // 'Abstand' zwischen zwei Iteratoren
>
{
public:
    Primes() : iterator_adaptor_(0) {} // jetzt ist base()==0
    friend boost::iterator_core_access;
private:
    T dereference() const
    {
        switch( base() )
        {
        case 0: return T(2);
        case 1: return T(3);
        }
        return T(6)*(base() >> 1) + (base() & 1? 1: -1);
    }
};

.. schon ist der Iterator fertig. Man kann nun mit den übliche Methoden *,++,--,[] darauf zugreifen.
siehe http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/iterator_adaptor.html

Gruß
Werner

[Die erinnerung]

Also. Ich habe jetzt einige Vorschläge umgesetzt und die Klasse noch ein bischen erweitert.

Das mit dem iterator habe ich bis jetzt noch nicht umgesetzt. Werde ich die Tage dann mal machen. Dennoch würde ich hier gerne auf Boost verzichten, da man das ja bräuchte, sollte ich die Klasse hier in eine Bibliothek umwandeln. Finde ich nicht so günstig. (Boost habe ich installiert. Ich verwende es auch gerne.)
Ebenfalls habe ich die Primes.cpp nicht umbenannt, da VC++ 2010 damit nicht wirklich zurechtkommt.

Ich habe den Code im Startpost aktualisiert und hier werde ich den Code auch nochmal posten!

Primes.h:

#ifndef Primes_H_
#define Primes_H_

#include <algorithm>
#include <cmath>
#include <fstream>
#include <vector>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>

template<class T = size_t, class Container = std::vector<T>>
class Primes
{
private:
	// Member fields/methods
	size_t internalCounter;

	// Static fields/methods
	static Container storedPrimes;
	static const T two;

	static void fillContainer();
	static bool internal_isPrime(const T& number);

	static std::string generateAutoSaveFileName();
	static unsigned int generateHash(const std::string& str);

public:
	// Constructors
	Primes();
	Primes(const T& number);

	// Member fields/methods
	Primes<T, Container>& operator++();
	Primes<T, Container>& operator--();

	const Primes<T, Container> operator++(int);
	const Primes<T, Container> operator--(int);

	const T& operator*();
	const T& operator[](size_t pos);

	// Static fields/methods
	static size_t getSize();
	static size_t getPointerPosition();
	static bool isPrime(const T& number);

	static void writeToStream(std::ostream& write_out);
	static void readFromStream(std::istream& read_in);

	static void writeToFile(const std::string& fileName);
	static void readFromFile(const std::string& fileName);

	static void autoSave();
	static void autoLoad();
};

// Initialize static fields

template<class T, class Container>
typename Container Primes<T, Container>::storedPrimes;
template<class T, class Container>
typename const T Primes<T, Container>::two = T(2);

#include "Primes.cpp"

#endif

Primes.cpp:

#ifndef Primes_CPP_
#define Primes_CPP_

#include "Primes.h"

// ======================
// Private static methods
// ======================

// static void fillContainer()
template<class T, class Container>
void Primes<T, Container>::fillContainer()
{
	if(storedPrimes.size() == 0)
	{
		storedPrimes.push_back(T(2));
		storedPrimes.push_back(T(3));
	}
}

// static bool internal_isPrime(const T& number)
template<typename T, typename Container>
bool Primes<T, Container>::internal_isPrime(const T& number)
{
    const T divisor_max = T(std::sqrt(long double(number)));

    for(Container::iterator it = storedPrimes.begin(); it != storedPrimes.end(); ++it)
	{
        if(*it > divisor_max)
			return true;

		if(number % *it == 0)
            return false;
	}

    return true;
}

// static std::string generateAutoSaveFileName()
template<typename T, typename Container>
std::string Primes<T, Container>::generateAutoSaveFileName()
{
	stringstream stream;
	string hash;

	stream << hex << generateHash(string(typeid(Primes<T, Container>).name()));
	hash = stream.str();
	std::transform(hash.begin(), hash.end(), hash.begin(), ::toupper);

	return string("autosave_#") + hash + string(".primes");
}

// static unsigned int generateHash(const std::string& str)
template<typename T, typename Container>
unsigned int Primes<T, Container>::generateHash(const std::string& str)
{
	unsigned int hash = 0;
	size_t size = str.size();

	for(size_t i = 0; i < size; ++i) 
		hash = 65599 * hash + str[i];

	return hash ^ (hash >> 16);
}

// ============
// Constructors
// ============

// Primes()
template<class T, class Container>
Primes<T, Container>::Primes() : internalCounter(0)
{
	fillContainer();
}

// Primes(const T& number)
template<class T, class Container>
Primes<T, Container>::Primes(const T& number) : internalCounter(pos)
{
	fillContainer();
}

// ==============
// Public methods
// ==============

// Primes<t, Container>& operator++()
template<class T, class Container>
Primes<T, Container>& Primes<T, Container>::operator++()
{
	++internalCounter;

	return *this;
}

// Primes<t, Container>& operator--()
template<class T, class Container>
Primes<T, Container>& Primes<T, Container>::operator--()
{
	--internalCounter;

	return *this;
}

// const Primes<t, Container> operator++(int)
template<class T, class Container>
const Primes<T, Container> Primes<T, Container>::operator++(int)
{
	Primes<T, Container> tmp(*this);
	++internalCounter;

	return tmp;
}

// const Primes<t, Container> operator--(int)
template<class T, class Container>
const Primes<T, Container> Primes<T, Container>::operator--(int)
{
	Primes<T, Container> tmp(*this);
	--internalCounter;

	return tmp;
}

// const T& operator*()
template<class T, class Container>
const T& Primes<T, Container>::operator*()
{
	return this-operator[](internalCounter);
}

// const T& operator[](size_t pos)
template<class T, class Container>
const T& Primes<T, Container>::operator[](size_t pos)
{
	internalCounter = pos;

	T currentNumber = storedPrimes.back();

	while(pos >= storedPrimes.size())
	{
		if((std::numeric_limits<T>::max() - currentNumber) < 2)
		{
			std::string message;
			std::stringstream stream;

			stream << pos;

			message = "An overflow occured while trying to generate the "
				    + stream.str()
					+ "th prime number. Your number type is likely too small!";

			throw std::overflow_error(message.c_str());
		}

		currentNumber += two;

		if(internal_isPrime(currentNumber))
			storedPrimes.push_back(currentNumber);
	}

	return *std::next(storedPrimes.begin(), pos);
}

// =====================
// Public static methods
// =====================

// static size_t getSize()
template<class T, class Container>
size_t Primes<T, Container>::getSize()
{
	return storedPrimes.size();
}

// static size_t getPointerPosition()
template<class T, class Container>
size_t Primes<T, Container>::getPointerPosition()
{
	return internalCounter;
}

// static bool isPrime(const T& number)
template<typename T, typename Container>
bool Primes<T, Container>::isPrime(const T& number)
{
    const T divisor_max = T(std::sqrt(long double(number)));

    for(Primes<T, Container> i; *i <= divisor_max; ++i)
        if(number % *i == 0)
            return false;

    return true;
}

// static void writeToStream(std::ostream& write_out)
template<typename T, typename Container>
void Primes<T, Container>::writeToStream(std::ostream& write_out)
{
	if(write_out)
	{
		size_t size = storedPrimes.size();
		const size_t bytesForT = sizeof(T);

		write_out.write((const char *) &size, sizeof(size_t));

		for(Container::iterator it = storedPrimes.begin(); it != storedPrimes.end(); ++it)
		{
			write_out.write((const char *) &*it, bytesForT);
		}
	}
}

// static void readFromStream(std::istream& read_in)
template<typename T, typename Container>
void Primes<T, Container>::readFromStream(std::istream& read_in)
{
	if(read_in)
	{
		size_t size;
		const size_t bytesForT = sizeof(T);
		T tmp;

		storedPrimes.clear();

		read_in.read((char *) &size, sizeof(size_t));

		storedPrimes.reserve(size);

		for(size_t i = 0; i < size; i++)
		{
			if(!read_in.good())
				throw ios_base::failure("Failed to read from stream!");

			read_in.read((char *) &tmp, bytesForT);

			storedPrimes.push_back(tmp);
		}
	}
}

// static void writeToFile(std::string& fileName)
template<typename T, typename Container>
void Primes<T, Container>::writeToFile(const std::string& fileName)
{
	std::ofstream write_file;

	write_file.open(fileName.c_str(), ios_base::binary | ios_base::out);
	writeToStream(write_file);
	write_file.close();
}

// static void readFromFile(std::string& fileName)
template<typename T, typename Container>
void Primes<T, Container>::readFromFile(const std::string& fileName)
{
	std::ifstream read_file;

	read_file.open(fileName.c_str(), ios_base::binary | ios_base::in);
	readFromStream(read_file);
	read_file.close();
}

// static void autoSave()
template<typename T, typename Container>
void Primes<T, Container>::autoSave()
{
	const char* const fileName = generateAutoSaveFileName().c_str();
	std::ifstream read_file;
	std::ofstream write_file;

	read_file.open(fileName, ios_base::binary | ios_base::in);

	if(write_file)
	{
		size_t size;

		read_file.read((char *) &size, sizeof(size_t));
		read_file.close();

		if(size < getSize())
		{
			write_file.open(fileName, ios_base::binary | ios_base::out);
			writeToStream(write_file);
			write_file.close();
		}
	}
	else
	{
		read_file.close();
	}
}

// static void autoSave()
template<typename T, typename Container>
void Primes<T, Container>::autoLoad()
{
	const char* const fileName = generateAutoSaveFileName().c_str();
	std::ifstream read_file;

	read_file.open(fileName, ios_base::binary | ios_base::in);

	if(read_file)
	{
		size_t size;

		read_file.read((char *) &size, sizeof(size_t));

		if(size > getSize())
		{
			read_file.close();

			read_file.open(fileName, ios_base::binary | ios_base::in);
			readFromStream(read_file);
		}
	}

	read_file.close();
}

#endif