sehr große zahl speichern

[nikolai]

hallo.
ich will ein programm schreiben, welches sehr große primzahlen berechnen soll.
dazu brauch ich eine variable, die in der lage ist eine 10millionen stellige zahl zu speichern.
wie erstelle ich einen ty/klasse die dazu in der lage ist?

[Knuddlbaer]

Such mal ein bisschen im Forum.
Die Frage nach sehr großen Zahlen gabs oft. Ok nich mit 10 Millionen Stellen Aber vllt. bringt es Dich dennoch weiter.

[nikolai]

ich finde nur 2 eiträge und die helfen mir nicht gerade weiter.

[PoRcUpInE]

du weißt schon dass das ewig dauert, primzahlen in der größenordnung zu suchen, aber wenns dich interessiert:
http://primes.utm.edu/primes/search.php?Number=100
http://www.mersenne.org/primenet/
Dazu musste dir erst mal nen guten Algorithmus eimfallen lassen, bzw irgendwo abgucken und dabei kommts dann wirklich auf jeden zusätzliuchen Aufruf, bzw jede zusätzlich Operation an. Und eine Implementierung mit den dazugehörigen Funktionen für eine Zahl wirst du wohl in Assembler implementieren müssen um überhaupt ein bissl Performance zu bekommen.

[nikolai]

ich weiß, dass ich nen guten algorythmus brauch.
ich habe eine möglichkeit gefunden,
nur 3 bis 4 zahlen dividieren zu müssen um herauszufinden ob eine zahl eine primzahl ist oder nicht, unabhängig von ihrer größe.
jetzt muß ich es nur noch schaffen, diese großen zahlen in meinen rechner zu bekommen. (würde es auch per hand machen können aber mein taschenrechner unterstützt ebenfalls nicht diese großen zahlen

[Cocaine]

nikolai schrieb:

ich habe eine möglichkeit gefunden,
nur 3 bis 4 zahlen dividieren zu müssen um herauszufinden ob eine zahl eine primzahl ist oder nicht, unabhängig von ihrer größe.

Irgendwie fällt's mir schwer, das zu glauben...

[CruelDiscovery]

naja.. jetzt hat ein student eine primzahl gefunden die über 6 millionen stellen hat und schon versucht jeder über die 10 millionen zu kommen um den jackpot von 100.000$ zu knacken

[nikolai]

fiel es mir auch als ich es gesehen habe.
habe es aber versucht mathematisch zu beweisen und es stimmte.
(habe auch keine fehler gemacht, hab es meinem mathe prof gezeigt und der kam auf das selbe ergebnis.)

ich habe jetzt nur das problem, dass ich es nicht schaffe zahlen in der größenordnung in meinen rechner zu bekommen

das verfahren findet sehr schnell (meist bei der dritten oder vierten division)
heraus, ob eine zahl KEINE primzahl ist,
ob eine zahl eine primzahl IST kann man allerdings bei der hälfte der zahl+1 beweisen.

[PoRcUpInE]

hört sich interessant an! Wenn ich im Moment nicht so viel mit lernen für die Zwischenklausur beschäftigt wär und die Weinachtsferien nicht mit nachholen von ner ganzen Menge zu tun hätte, würd ich mich mal dran setzen. Aber wenn ich so drüber nachdenke ist das ein riesenaufwand, vor allem denk ich wär eine Implementierug in Assembler immernoch am sinnvollsten! Solltest du mal drüber nachdenken!

Gruß
Mike

[PoRcUpInE]

mir ist grad nochwas eingefallen! ich weis nicht wie dein algorithmus aussieht, aber viel kannst du ja die operationen so umänderen, dass du sie auf das mersenne-format anwenden kannst! dann bräuchteste du keine so großen zahlen zu speichern

[nikolai]

ich habe mich mit mersenne nicht so sehr beschäftigt.
du meinst mit format: 2^1398269-1 ???
das ist ungünstig, da ich wirklich divisionen ausführen muß.

von daher wäre eine möglichkeit einen so großen datentyp anzulegen für mich wahrscheinlich die beste lösung. aber wie? muß ich dann alle rechenoperationen überlagern? das wird bei der division ganzschön haarig

[PoRcUpInE]

das problem wird nicht das überlagern sondern das darstellen im Speicher! (Da fängts schon an) Du musst ja in irgendeiner Weise darstellen wieviel Speicher du willst/brauchst und das bei 10 millionen Stellen! Ich meine damit das du irgendwo in deinem Code eine Konstante stehen hast die den Speicherplatzbedarf für 10mio Ziffern angibt! Und diese Konstante wird der Compiler nicht akzeptieren (geh ich mal davon aus) und genau da fangen die Probleme schon an! Was anderes fällt mir im Moment nämlich auch nicht ein!

Gruß
Mike

[Shade Of Mine]

PoRcUpInE schrieb:

Und eine Implementierung mit den dazugehörigen Funktionen für eine Zahl wirst du wohl in Assembler implementieren müssen um überhaupt ein bissl Performance zu bekommen.

also mein Compiler macht in den meisten Fällen wesentlich effizienteren Code als ich. Meine ASM Kenntnisse sind beschränkt, aber mein Compiler hängt mich da fast immer sehr weit ab.

ASM kann man nur verwenden um eine bestime Stelle schneller zu machen (nachdem der Profiler gezeigt hat, dass es nötig ist)

[nikolai]

könnten wir bitte wieder zum thema kommen "wie speichere ich eine so große zahl?"?
gibt es denn keine möglichkeit "int" zu erweitern?
ich hatte erst an ein array gedacht, aber da ist die frage wie dividiere und multipliziere ich.

[Christoph]

Schau dir mal GNU MP an.

[nikolai]

To build MP, you first have to configure it for your CPU and operating system. You need a C compiler, preferably GCC, but any reasonable compiler should work. And you need a standard Unix `make' program, plus some other standard Unix utility programs.*

ich schreibe mit dem visuell c++ 6.0

ich würde gern bei der sprache c++ bleiben und keinen kuddelmuddel mit unix anfangen.

gnu-mp sieht aber sonster sehr interessant aus.

[Entyl_Sa]

Hallo,

mein Bruder hat mal ein Programm geschrieben was mit so riesigen natürlichen Zahlen rechnen kann, weis jetzt nicht wie performant das ist und da ist auch ein wenig inline Assembler drin, aber es ist mir VC++ geschrieben. Kannst ja mal gucken ob du damit was anfangen kannst:

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

class Ziffer {
public:
  Ziffer ();
  Ziffer (int , Ziffer * ); 
  ~Ziffer () {};
  int z;
  Ziffer * n;
};

class Pool {
public:
	Pool();
	~Pool();

	Ziffer* get (int , Ziffer*);
	void term (Ziffer * &);
	Ziffer p [1000000];
	Ziffer * nextfree;
};

class Iterator {
	friend class Zahl;
public:
	Iterator () ;
	Iterator (Ziffer* a) ;
	void operator++ ();
	bool operator!= (Iterator);
	bool operator== (Iterator);
	int & operator* ();
private:
	void weiter();
	Ziffer* pos;
};

class Zahl {
	friend class Iterator;
public:
	Zahl ();
	Zahl (string);
	Zahl (Zahl &);
	~Zahl () {pool.term(anfang);}
	void ausgabe ();
	Ziffer* start ();
	Zahl & operator= (Zahl &);
	Zahl operator* (Zahl &);
	void operator*= (Zahl &);
	Zahl operator* (int);
	void operator*= (int);
	void operator+= (Zahl &);
	Zahl operator+ (Zahl &);
	Zahl operator- (Zahl &);
	void operator-= (Zahl &);
	Zahl operator/ (Zahl &);
	Zahl operator% (Zahl &);
	void operator%= (Zahl &);
	Zahl operator^ (Zahl &);
	Zahl hochmod (Zahl &, Zahl &);
	void operator++ ();			
	void operator-- ();			
	void mulzwei();
	void divzwei ();
	bool ungerade ();
	bool gerade();
	bool operator == (Zahl &);
	bool operator != (Zahl &);
	bool operator < (Zahl &);
	bool operator > (Zahl &);
	bool operator <= (Zahl &);
	bool operator >= (Zahl &);
private:
	void weiter();
	void weiter(int);
	void ende();

	Ziffer * anfang;
	static Pool pool;
};

inline Iterator::Iterator () : pos(0) {}

inline Iterator::Iterator(Ziffer* a) {pos = a;}

inline void Iterator::operator++ () {
	pos = pos->n;
}

inline int & Iterator::operator* () {
	return pos->z;
}

inline bool Iterator::operator!= (Iterator i) {
	return pos != i.pos;
}

inline bool Iterator::operator== (Iterator i) {
	return pos == i.pos;
}

Pool::~Pool () {}

Ziffer* Pool::get (int i, Ziffer * z) {    
	Ziffer* erg;
	erg = nextfree;
	nextfree = nextfree->n;
	erg->n = z;
	erg->z = i;
	return erg;
}

void Pool::term ( Ziffer* &z) {      
        Ziffer* i;
	for(i = z; i->n != 0;i = i->n);
	i->n = nextfree;
	nextfree = z;
	z = 0;
}

Pool::Pool () {
	for(int i= 0; i<999999;++i)
		p[i].n = &(p[i+1]);
	nextfree = &(p[0]);
	p[999999].n = 0;
}

inline Ziffer::Ziffer () :z(0), n(0) {}

inline Ziffer::Ziffer (int pz, Ziffer * pn) :z(pz), n(pn) {}

inline Ziffer* Zahl::start () {
	return anfang;
}

inline void Iterator::weiter () {
        Ziffer* t;
	for (t = pos; t->n != 0; t = t->n);
	t->n = Zahl.pool.get(0, 0);
}

inline void Zahl::weiter () {
        Ziffer* t;
	for (t = anfang; t->n != 0; t = t->n);
	t->n = pool.get(0, 0);
}

inline void Zahl::weiter (int i) {
        Ziffer* t;
	for (t = anfang; t->n != 0; t = t->n);
	t->n = pool.get(i, 0);
}

void Zahl::ende () {
	if (anfang->n == 0) return;		
	Ziffer* del = anfang;
	Ziffer* t = anfang;
	while (t->n != 0) {
		t = t->n;
		if(t->z != 0) del = t;
	}
	if(del->n) pool.term(del->n);
}

Zahl & Zahl::operator= (Zahl & z) {
	pool.term(anfang);
	Iterator i(z.start());
	anfang =pool.get(*i, 0);
	Ziffer *a = anfang;
	++i;
	while (i.pos) { 
		a->n = pool.get(*i, 0);
		a = a->n;
		++i;
	}
	return *this;
}

Zahl::Zahl (Zahl & z) {

	z.ende();
	Iterator i(z.start());
	anfang = pool.get(*i, 0);
	Ziffer* a= anfang;
	++i;
	while (i.pos) {
		a->n = pool.get(*i, 0);
		a = a->n;
		++i;
	}
}

inline Zahl::Zahl () {
	anfang = pool.get(0, 0);
}

Zahl::Zahl (string a) {
	anfang = 0;
	int pos = a.length() -1;
	int erg = 0;
	for (int i=0; i<9 && pos>= 0;++i){
		erg += ((a.at(pos)-48) * pow(10, i));
		--pos;
	}
	anfang = pool.get(erg,0);
	Ziffer* p = anfang;
	while(pos>=0) {
		erg = 0;
		for (int i=0; i<9 && pos>= 0;++i){
			erg += ((a.at(pos)-48) * pow(10,i));
			--pos;
		}
		p->n = pool.get(erg,0);
		p = p->n;
	}
}

void Zahl::ausgabe () {
	(*this).ende();
	int aus, anzahl = 0;
	Iterator b;
	for (Iterator p = Iterator((*this).start()); p != b; ++p) {
		aus = *p;
		_asm push aus;
		++anzahl;
	}
	_asm pop aus;
	cout<<aus;
	--anzahl;
	for( int i=anzahl; i>0; --i){
		_asm pop aus;
		for(int index = 100000000;aus < index && 1 < index; index /=10) cout<<"0";
		cout<<aus;
	}
	cout<<" ";
}

Zahl Zahl::operator+ (Zahl  &i) {
	Zahl erg;
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while (erste.pos && zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *erste + *zweite;
		if(uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis>= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite; ++ergebnis;
	}
	while (erste.pos) {
		ergebnis.weiter();
		*ergebnis = *erste;
		if (uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis >= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++erste; ++ergebnis;
	}
	while (zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *zweite;
		if (uebertrag) ++(*ergebnis);
		uebertrag = false;
		if(*ergebnis >= 1000000000) {
			*ergebnis -= 1000000000;
			uebertrag = true;
		}
		++zweite; ++ergebnis;
	}
	if(uebertrag) *ergebnis = 1;

	return erg;
}

void Zahl::operator+= (Zahl  &i) {

	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while (erste.pos && zweite.pos) {
		*erste += *zweite;
		if(uebertrag) ++(*erste);
		uebertrag = false;
		if(*erste>= 1000000000) {
			*erste -= 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite;
	}
	while (erste.pos) {
		if (uebertrag) ++(*erste);
		uebertrag = false;
		if(*erste >= 1000000000) {
			*erste -= 1000000000;
			uebertrag = true;
		}
		++erste;
	}
	if(erste == 0) {
		Iterator ende((*this).start());
		ende.weiter();	
		while (ende.pos->n) ++ende;

		while (zweite.pos) {
			*ende = *zweite;
			if (uebertrag) ++(*ende);
			uebertrag = false;
			if(*ende >= 1000000000) {
				*ende -= 1000000000;
				uebertrag = true;
			}
			ende.weiter();
			++zweite; ++ende;
		}
	}
	if(uebertrag) *erste = 1;

	return;
}

Zahl Zahl::operator- (Zahl &i) {
	Zahl erg;
	if(i > *this) {
		pool.term(erg.anfang);
		return erg;
	}
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while(erste.pos && zweite.pos) {
		ergebnis.weiter();
		*ergebnis = *erste - *zweite;
		if (uebertrag) --(*ergebnis);
		uebertrag = false;
		if (*ergebnis < 0) {
			*ergebnis += 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite; ++ergebnis;
	}

	while (erste.pos) {
		ergebnis.weiter();
		*ergebnis = *erste;
		if (uebertrag) --(*ergebnis);
		uebertrag = false;
		if(*ergebnis < 0) {
			*ergebnis += 1000000000;
			uebertrag = true;
		}
		++erste; ++ergebnis;
	}

	return erg;
}

void Zahl::operator-= (Zahl &i) {
	Zahl erg;
	if(i > *this) {
		pool.term(erg.anfang);
		*this = erg;
		return;
	}
	Iterator erste((*this).start());
	Iterator zweite(i.start());
	bool uebertrag = false;

	while(erste.pos && zweite.pos) {
		*erste -= *zweite;
		if (uebertrag) --(*erste);
		uebertrag = false;
		if (*erste < 0) {
			*erste += 1000000000;
			uebertrag = true;
		}
		++erste; ++zweite;
	}

	while (erste.pos) {
		if (uebertrag) --(*erste);
		uebertrag = false;
		if(*erste < 0) {
			*erste += 1000000000;
			uebertrag = true;
		}
		++erste;
	}
}

bool Zahl::operator == (Zahl & i) {
	(*this).ende();
	i.ende();
	Iterator eins(i.start());
	Iterator zwei((*this).start());

	while(eins.pos && zwei.pos) {
		if(*eins != *zwei) return false;
		++eins; ++zwei;
	}

	if(!(eins.pos) && !(zwei.pos)) return true;
	else return false;
}

inline bool Zahl::operator != (Zahl & i) {
	if(i == (*this)) return false;
	else return true;
}

bool Zahl::operator < (Zahl & i) {
	(*this).ende();
	i.ende();
	Iterator eins(i.start());
	Iterator zwei((*this).start());
	bool erg = false;

	while(eins.pos && zwei.pos) {
		if(*eins < *zwei) erg = false;
		if(*eins > *zwei) erg = true;
		++eins; ++zwei;
	}
	if(eins.pos) erg = true;
	if(zwei.pos) erg = false;
	return erg;
}

inline bool Zahl::operator > (Zahl & i) {
	if(*this < i)return false;
	if(*this == i) return false;
	return true;
}

inline bool Zahl::operator <= (Zahl & i) {
	if(*this > i) return false;
	return true;
}

inline bool Zahl::operator >= (Zahl & i) {
	if(*this < i) return false;
	return true;
}

Zahl Zahl::operator * (int i) {
	Zahl erg;
	if (i == 1) return *this;
	if (i == 0) return erg;
	if (i == 1000000000) {
		erg = *this;
		erg.anfang= pool.get(0, erg.anfang);
		return erg;
	}
	Iterator ergebnis(erg.start());
	Iterator erste((*this).start()); 
	int uebertrag = 0;

	while(erste.pos) {
		ergebnis.weiter();
		int eins = *erste;
		int zwei;
		int drei = i;
		_asm mov eax, eins
		_asm mov edx, drei
		_asm mul edx
		_asm mov ecx, 1000000000
		_asm div ecx
		_asm add edx, uebertrag
		_asm adc eax,0
		_asm mov zwei, edx
		_asm mov uebertrag, eax
		*ergebnis = zwei;
		if (*ergebnis >= 1000000000) {
			uebertrag += *ergebnis / 1000000000;
			*ergebnis %= 1000000000;
		}
		++ergebnis; ++erste;
	}
	if(uebertrag) *ergebnis = uebertrag;
	erg.ende();

	return erg;
}

void Zahl::operator *= (int i) {
	if (i == 1) return;
	Zahl erg;
	if (i == 0) {*this = erg; return;}

	Iterator ergebnis(erg.start());
	Iterator erste((*this).start());
	int uebertrag = 0;

	while(erste.pos) {
		ergebnis.weiter();
		int eins = *erste;
		int zwei;
		int drei = i;
		_asm mov eax, eins
		_asm mov edx, drei
		_asm mul edx
		_asm mov ecx, 1000000000
		_asm div ecx
		_asm add edx, uebertrag
		_asm adc eax,0
		_asm mov zwei, edx
		_asm mov uebertrag, eax
		*ergebnis = zwei;
		if (*ergebnis >= 1000000000) {
			uebertrag += *ergebnis / 1000000000;
			*ergebnis %= 1000000000;
		}
		++ergebnis; ++erste;
	}
	if(uebertrag != 0) *ergebnis = uebertrag;
	erg.ende();

	*this = erg;
}

Zahl Zahl::operator* (Zahl & i) {
	Zahl erg;
	Iterator eins (i.start());
	Zahl zwischen;
	int index = 1;
	while(eins.pos) {
		zwischen = *this * *eins;
		for(int i = index; i >= 2; --i)zwischen.anfang = pool.get(0, zwischen.anfang);
		erg += zwischen;
		++eins; ++index;				
	}
	return erg;
}

void Zahl::operator*= (Zahl & i) {
	Zahl erg;
	Iterator eins (i.start());
	while(eins.pos) {
		erg += (*this) * *eins;
		++eins;
		(*this).anfang = pool.get(0, (*this).anfang);
	}
	*this = erg;
}

Zahl Zahl::operator% (Zahl & i) {
	Zahl enderg;
	if(i > *this) return *this;
	Zahl zwierg;
	Zahl eins("1");
	int mul = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= mul;
			sub *= mul;
		}
	}
	div.ende();
	return div;	
}

void Zahl::operator%= (Zahl & i) {
	Zahl enderg;
	if(i > *this) return;
	Zahl zwierg;
	Zahl eins("1");
	int mul = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= mul;
			sub *= mul;
		}
	}
	div.ende();
	*this = div;	
}

Zahl Zahl::operator/ (Zahl & i) {

	Zahl enderg;
	if(i > *this) return enderg;
	Zahl zwierg;
	string s = "1";
	Zahl eins(s);
	int zehn = 10;
	Zahl div = *this;
	while(div >= i) {
		Zahl sub = i;
		zwierg = eins;
		while(div >= sub) {
			enderg += zwierg;
			div -= sub;
			zwierg *= zehn;
			sub *= zehn;
		}
	}
	return enderg;
}

void Zahl::divzwei () {
	Iterator i((*this).start());
	Iterator next((*this).start());
	if(anfang->n == 0) {(*i) >>=1; return;}
	++next;
	while(next.pos) {
		*i >>=1;
		if(*next & 1) *i += 500000000;
		++next; ++i;
	}
	*i >>=1;
	return;
}

void Zahl::mulzwei() {
	Iterator i((*this).start());
	bool carry = false;
	while(i.pos) {
		*i <<=1;
		if(carry) ++(*i);
		if(*i >= 1000000000) carry = true;
		else carry = false;
		++i;
	}
	if(carry) (*this).weiter(1);
	return;
}

inline bool Zahl::ungerade() {
	return (anfang->z & 1);
}

Zahl Zahl::operator^ (Zahl & i) {

	Zahl enderg;
	Zahl eins ("1");
	if (i == enderg) return eins;
	if (i == eins) return *this;
	Zahl zwierg = *this;
	Zahl null;
	enderg = eins;
	while(i != null) {
		if(i.ungerade()) enderg *= zwierg;
		i.divzwei();
		zwierg *= zwierg;
	}
	return enderg;
}

Zahl Zahl::hochmod (Zahl & i, Zahl & a) {

	Zahl enderg;
	Zahl eins ("1");
	Zahl null ("0");
	*this %= a;
	if (a == null) return null;
	if (i == enderg) return eins;
	if (i == eins) return *this;
	Zahl zwierg = *this;
	enderg = eins;
	while(i != null) {
		if(i.ungerade()){ 
			enderg *= zwierg;
			enderg %= a;
		}
		i.divzwei();
		zwierg *= zwierg;
		zwierg %= a;
	}
	return enderg;
}

inline void Zahl::operator ++ () {
	Zahl eins("1");
	*this += eins;
}

inline void Zahl::operator -- () {
	Zahl eins("1");
	*this -= eins;
}

Pool Zahl::pool;

int main () {
	int i;
	cout<<"Bitte geben Sie die Art der Rechnung an die Sie vornehmen wollen: "<<endl;
	cout<<"multiplikation (1)"<<endl;
	cout<<"division (2)"<<endl;
	cout<<"modulo (3)"<<endl;
	cout<<"subtraktion (4)"<<endl;
	cout<<"addition (5)"<<endl;
	cout<<"potenzieren (6)"<<endl;
	cout<<"a hoch b mod c (7)"<<endl;
	cin>>i;
	string s;
	cout<<"Bitte a eingeben: ";
	cin>>s;
	Zahl a(s);
	cout<<"Bitte b eingeben: ";
	cin>>s;
	Zahl b(s);
	if(i == 7) {cout<<"Bitte c eingeben: "; cin>>s;}
	Zahl c(s);
	cout<<"a = ";
	a.ausgabe();
	cout<<endl<<"b = ";
	b.ausgabe();
	if(i == 7) {cout<<endl<<"c = "; c.ausgabe();}
	cout<<endl;
	if(i<2 || i>7) {cout<<"a = a * b"<<endl; a *= b;}
	if(i == 2) {cout<<"a = a / b"<<endl; a = a / b;}
	if(i == 3) {cout<<"a = a % c"<<endl; a %= b;}
	if(i == 4) {cout<<"a = a - b"<<endl; a -= b;}
	if(i == 5) {cout<<"a = a + b"<<endl; a += b;}
	if(i == 6) {cout<<"a = a ^ b"<<endl; a = a^b;}
	if(i == 7) {cout<<"a = a^b%c"<<endl; a = a.hochmod(b,c);}
	a.ausgabe(); cout<<endl;
	cout<<"zum beenden etwas eingeben"<<endl;
	cin>>s;
	return 0;
}

[nikolai]

habe ein paar ansätze aus dem quelli geklaut.
danke an deinen bruder und dich.
gibt es nicht für solche probleme (wie speichere ich große zahlen) ne extra bibliothek?wie die gnu-mp nur halt für windows?

[nikolai]

nach ewig langem suchen habe ich nun schließlig (gott sei dank) was schönes gefunden:
für jeden den es interessiert und große zahlen zum verschlüsseln oder ähnlichem braucht:
http://www.acid-code.ch/~samuel/BigInt.zip

[japro]

nikolai schrieb:

das verfahren findet sehr schnell (meist bei der dritten oder vierten division)
heraus, ob eine zahl KEINE primzahl ist,
ob eine zahl eine primzahl IST kann man allerdings bei der hälfte der zahl+1 beweisen.

öööh also zum beweisen musst du eeeeeeeeeeeeeeeeextrem viele divisionen durchführen. also angnommen deine zahl hat diese 10mio stellen dann musst du so in etwa
1/2*10^10000000 divisionen durchführen um zu beweisen, dass die zahl prim ist

gehen wir mal von ein hammerrechner aus der eine division in einem takt ausführt und das bei 1 Thz! also 1 billion divisionen pro sekunde also 10^12!
ok also braucht unser monstercomputer 1/2*10^9999988 sekunden das sind scho schätzungsweise öhm 10^9999981 jahre..... dein pc mus ne hammer uptime haben... oder hab ich da irgendwas entscheidendes übersehen?