laaaaanger array

[pixartist]

ich hab n primzahlen programm gebastelt(bin noch ganz neu):

#include <iostream.h>
#include <math.h>
class getPrim
{
private:
	int *array;
	int got;
	int till;
	int from;
	int anzahl;
	int till2;
	int laenge;
public:
getPrim(int Mtill) {
	anzahl = 0;
	laenge = 0;
	till = Mtill;
	from = 1;
	till2 = sqrt(till);
	array = new int[till-from];
}
void showPrim()
{
	for(int g = 0; g<till-from; ++g) 
	{
		if(from+g%2 != 0)
		{
			++laenge;
			array[g] = from+g;
		}
	}
	for(int i = 0; i<sqrt(laenge); ++i) 
	{
		if(array[i] == 1)
			array[i] = 0;
		if(array[i] != 0) 
		{
			for(int x = i+1; x<=laenge; ++x) 
			{
				if(array[x]%array[i] == 0)
				{
					array[x] = 0;
				}
			}

		}
	}
	for(int b = 0; b<=laenge;++b) 
	{
		if(array[b] != 0) 
		{
			cout<<array[b]<<endl;
			++anzahl;
		}
	}
	cout<<"Also gibt es von "<<from<<" bis "<<till<<" genau "<<anzahl<<" Primzahlen!"<<endl;
}
};
void main()
{
	while(true)
	{
		int a = -1;
		cout<<"Bis zu welcher Zahl soll nach Primzahlen gesucht werden? (0 = Exit)"<<endl;	
		while(0>a)
		{
			cout<<"bis:"<<endl;
			cin>>a;
			if(a == 0) {
				return;
			}
		}
		cout<<"Gibt es die Primzahlen:"<<endl;
		getPrim prim(a);
		prim.showPrim();

	}
}

wenn ich jetzt 1000000 (ne million) eingebe, dann dauert es erstma 3 sekunden oder so bis er anfängt die zahlen auszugeben. Wenn ich zehn millionen angebe, dann passiert nix mehr aber wie soll man denn diese zahlenlöschung ohne nen array machen? kann ich die länge erhöhen?

edit: auch mit 10mille gehts...die erstellung des arrays dauert aber ewig...

[volkard]

ich hab's etappenweise gemacht, damit der speicher keine grenze mehr darstellt.

#ifndef PRIMEGENERATOR_H
#define PRIMEGENERATOR_H

#include "BitField.h"
#include "Prime.h"
#include "ostream.h"

/*Mit dem Sieb des Eratostenes werden Primzahlen gesucht. Weil ich nicht den 
Speicher für 2^32 Bits habe, geschieht das Abschnittweise. Dabei ist zu beachten, 
daß für einen neuen Abschnitt von z1 bis z2 alle Teiler bis sqrt(z2) ausgestrichen 
werden müssen. Um das zu beschleunigen, gibt es noch ein kleines Sieb, das zur 
Generierung der Streich-Zahlen zuständig ist. Das wiederum wird nicht mehr von 
einem Sieb versorgt, sondern nur von der Funktion nextPrime().
*/
namespace PrimeGeneratorPrivate{
const u32 BIGSIZE=128*256;//Soll ja in den 1st-Level-Cache des Prozessors passen
const u32 SMALLSIZE=256;

class PrimeGeneratorLevel0{
private:
	u32 pos;
public:
	u32 findFirst(){
		pos=2;
		return pos;
	}
	u32 findNext(){
		pos=nextPrime(pos);
		return pos;
	}
};
class PrimeGeneratorLevel1{
private:
	enum{SIZE=SMALLSIZE};
	BitField field;
	u32 pos;
	u32 start;
public:
	PrimeGeneratorLevel1():
	field(SIZE){
	}
	u32 findFirst(){
		for(u32 t=3;t*t<=2*SIZE;t+=2)
			for(u32 s=t+t/2;s<SIZE;s+=t)
				field.set(s);
		pos=0;
		start=0;
		return 2;
	}
	void calculateNextPage(){
		do{
			start+=2*SIZE;
			field.clearAll();
			PrimeGeneratorLevel0 p;
			p.findFirst();
			for(u32 t=p.findNext();t*t<=start+2*SIZE;t=p.findNext()){
				u32 s=(t-start%t)%t;s+=(s%2==0?t:0);s/=2;
				while(s<SIZE){
					field.set(s);
					s+=t;
				}
			}
			pos=field.findFirstFalse();
		}while(pos==u32(-1));
	}
	u32 findNext(){
		pos=field.findNextFalse(pos);
		if(pos==u32(-1)){
			calculateNextPage();
		}
		return 2*pos+start+1;
	}
};
class PrimeGeneratorLevel2{
private:
	enum{SIZE=BIGSIZE};
	BitField field;
	u32 pos;
	u32 start;
public:
	PrimeGeneratorLevel2():
	field(SIZE){
		start=u32(-1);
	}
	u32 findFirst(){
		if(start!=0){
			for(u32 t=3;t*t<=2*SIZE;t+=2){
				for(u32 s=t+t/2;s<SIZE;s+=t)
					field.set(s);
			}
			start=0;
		}
		pos=0;
		return 2;
	}
	void calculateNextPage(){
		do{
			u32 old=start;
			start+=2*SIZE;
			if(start<old)
				pos=u32(-1);
			field.clearAll();
			PrimeGeneratorLevel1 p;
			p.findFirst();
			for(u32 t=p.findNext();t*t<=start+2*SIZE;t=p.findNext()){
				u32 s=(t-start%t)%t;s+=(s%2==0?t:0);s/=2;
				while(s<SIZE){
					field.set(s);
					s+=t;
				}
			}
			pos=field.findFirstFalse();
		}while(pos==u32(-1));
	}
	u32 findNext(){
		pos=field.findNextFalse(pos);
		if(pos==u32(-1)){
			calculateNextPage();
			if(pos==u32(-1)) return pos;
		}
		return 2*pos+start+1;
	}
};
inline bool test(){
	cout<<"testing class PrimeGenerator:\n";
	PrimeGeneratorLevel2 p;
	PrimeGeneratorLevel0 ps;

	u32 i=p.findFirst();
	u32 is=ps.findFirst();
	u16 c=0;
	while(i<1000000000){
		if(!++c) cout<<i<<'\r';
		if(i!=is){
			cout<<"Fehler bei "<<i<<'\n';
			return false;
		}
		i=p.findNext();
		is=ps.findNext();
	}
	cout<<"OK\n";
	return true;
}

}//namespace PrimeGeneratorPrivate

typedef PrimeGeneratorPrivate::PrimeGeneratorLevel2 PrimeGenerator;

/*
class PrimeTwinGenerator
{//nicht getestet!!!
private:
	PrimeGenerator pg;
	u32 pos;
public:
	u32 findFirst()
	{
		pg.findFirst();
		pg.findNext();
		pos=pg.findNext();
		return 3;
	};
	u32 findNext()
	{
		u32 o;
		do
		{
			o=pos;
			pos=pg.findNext();
		}while(pos-o!=2);
		return o;
	};
};*/

#endif

[pixartist]

ups schon geklährt...