Klassenvorstellung: Primzahlen

[Die erinnerung]

Hallo.

Ich würde euch heute gerne meine Primzahlenklasse vorstellen.
Ich werde sie grob erklären und den Quellcode posten. Da ich leider ein wenig aus der Übung bin, bin ich mir sicher, dass man die Klasse noch (deutlich) im Design, Codedesign und Performance verbessern kann.
Sonstige Verbesserungsvorschläge, Lob oder Kritik sind gerne gesehen.

Hier ist der Code:

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;

	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

Man instanziert die Klasse ganz normal mit einem numerischen Typ und optional einen Container.
Besipiel:

Primes<unsigned int> primzahlen;
Primes<size_t, std::deque<size_t>> primzahlen2(5);

Man kann auf die n-te Primzahl [i](0 ist die erste Primzahl (2). Wie beim Array. Dort beginnt man auch mit 0.)* ganz einfach über den [] -Operator zugreifen. Ist diese Zahl bereits berechnet, wird sie zurückgegeben. Ist sie noch nicht berechnet, werden alle noch nicht berechneten Primzahlen, bis zur Gewünschten, berechnet.

std::cout << primzahlen[2] << std::endl; // 5
std::cout << primzahlen[20] << std::endl; // Berechnet alle Primzahlen bis zur 21. (Also index 20)
std::cout << primzahlen[10] << std::endl; // Bereits berechnet. Gibt sie einfach zurück

Die Klasse hat außerdem einen internen "Index-Zeiger". Das ist einfach eine Zahl, die sich den aktuellen Index merkt.
Möchte man auf die Primzahl am aktuellen Index zugreifen, verwendet man den Derefferenzeirungsoperator. Mit den Inkrement- und Dekrementoperatoren kann man den Index auch manipulieren. Ein Postfix Inkrement oder Dekrement, gibt die eine Kopie des aktuellen Objekts zurück und inkrementiert oder dekrementiert den Index dann. Beim Präfix ist es genau umgekerht.

Der Index-Operator [] setzt den Index außerdem noch auf den übergebenen Wert.

Primes<unsigned int> primzahlen(2);

std::cout << *primzahlen << std::endl;
          << *(primzahlen++) << std::endl
          << *primzahlen << std::endl;
// 5
// 5
// 7

std::cout << *primzahlen << std::endl
          << *(--primzahlen) << std::endl
          << *primzahlen << std::endl;
// 7
// 5
// 5

Ich hoffe ich habe die Klasse soweit ausreichend erklärt.

Wie ebreits erwähnt, freue ich mir sehr über Feedback!

[volkard]

Ich fürchte, vor lauter Verliebtheit in die Generizität verlierst Du den Blick für was gebraucht wird und verbaust Dir Optimierungsmöglichkeiten.

bool prime? Wenn man künstliche Variablen braucht, Flags, um goto zu sparen, ist es immer eine Überlegung wert, ob man nicht etwas in eine Funktion auslagern möchte.

Und was soll das denn?!

if(!(prime = (currentNumber % *it) != 0))

[Die erinnerung]

volkard schrieb:

Ich fürchte, vor lauter Verliebtheit in die Generizität verlierst Du den Blick für was gebraucht wird und verbaust Dir Optimierungsmöglichkeiten.

Das ganze möchte ich vieleicht später als kleine Bibliothek anbieten. Und da es bistimmt Klassen gibt, die größere Zahlen als unsigned long long zulassen, wollte ich diese Möglichkeit dem Programmierer nicht wegnehemen.
ich könnte allerdings noch einen default-Type für T festlegen...

volkard schrieb:

bool prime? Wenn man künstliche Variablen braucht, Flags, um goto zu sparen, ist es immer eine Überlegung wert, ob man nicht etwas in eine Funktion auslagern möchte.

Ich habe eigentlich gelernt, dass man goto 's um jeden Preis vermeiden sollte.

volkard schrieb:

Und was soll das denn?!

if(!(prime = (currentNumber % *it) != 0))

Die Zeile überprüft, ob die aktuelle Zahl currentNumber duch den Wert im Iterator it teilbar ist und speichert den Wert dann in prime . Das wird dann invertiert, weil ich die Schleife nur verlassen möchte, wenn der Test fehlgeschlagen ist. Also es sich um keine Primzahl handelt.
Die Flag brauche ich, um nach der Schleife zu entscheiden, ob ich die Zahl currentNumber in der Liste der Primzahlen speichern soll, oder nicht.

[hustbaer]

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.

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

Statt sprintf_s würde ich einen stringstream verwenden - die bessere Performance von sprintf_s spielt hier keine Rolle, und mit stringstream hast du eine potentielle Fehlerquelle (zu kleiner Puffer) weniger.

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 .

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.

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.

Wieso du 2x ++ machst statt 1x += 2 ist mir auch nicht klar.

Dein Overflow-Test ist für signed Typen undefiniert. Besser wäre vor dem += 2 zu prüfen ob es noch geht. z.B. über (std::numeric_limits<T>::max() - currentNumber) >= 2 .
(Wenn du natürlich fix size_t verwendest, das per Definition unsigned ist, dann ist der Overflow-Test wieder OK.)

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.

[hustbaer]

Die erinnerung schrieb:

Ich habe eigentlich gelernt, dass man goto 's um jeden Preis vermeiden sollte.

Und du hast nicht verstanden was volkard dir sagen wollte.
Du sollst da kein goto hinschreiben sondern den Loop in eine Funktion auslagern.

[lolalter]

if( ! (prime = (currentNumber % *it) ! = 0))

[hustbaer]

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";

[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