Primtal på hjernen...

Kommer lige i tanke om at den person jeg har konveseret med på nyhedsgrupperne har givet mig noget kode som jeg ikke fatter en bregne af, men det skal da ikke forhindre andre i at blive inspireret og evt. forklare det for mig ;-)

her er koden med kommentarer:

class primes: 
  public std::iterator< std::forward_iterator_tag, unsigned long > 
{ 


public: 
  primes(); // create a sentinel object 
  explicit primes(unsigned long m); // 'm' is how many primes 
                                    // that will be in the sequence 
  unsigned long operator*() const;  // return the current prime 
  primes& operator++();             // advance to the next prime 
  primes operator++(int) { primes tmp(*this); ++(*this); return tmp; } 
  friend bool operator==(const primes& lhs, const primes& rhs); 
     // if one of the inputs is a sentinel and the other is at the end 
     // of its sequence, return true. Otherwise check to see if the 
     // two inputs are pointing to the same prime, and will have the 
     // same effect if advanced. 
}; 


bool operator!=(const primes& lhs, const primes& rhs) { 
  return !(lhs == rhs); 
} 


// With the above, you can generate your primes file without taking up lots of memory: 

int main() { 
  ofstream file("primes.txt"); 
  copy(primes(/*number of primes to write*/), primes(), 
    ostream_iterator<unsigned long>(file, "\\n")); 
} 

// If you write the primes class right, the memory requirements of the 
// above will remain constant no matter how many primes you write to the 
// file. 
// ---
// Open the file as binary. Reading and writing to it will be tricker 
// though. Look up the ifstream::read and ofstream::write functions. 
// (hint) I would use a union for this: 


union Buffer { 
  char c[sizeof(unsigned long)]; 
  unsigned long i; 
}; 

Har fiflet lidt med din kode og dermed fjernet is_prime:

// Bruger [b]index[/b] i stedet for [b]i[/b] for at undgå skrå tekst
for (test = P.back() + 2; test != 1; test+=2, root = sqrt(test)) {
	for (index = 1; P[index] <= root; index++)
		if(test % P[index]==0) {test+=2; root=sqrt(test); index=0;} // "index=0" idet FOR laver en index++ i næste loop
	if(test <= 0xFFFFFFFF) P.push_back(test);
	primes << P.back() << endl;
}

Har fiflet lidt med din kode og dermed fjernet is_prime:

Kode 

// Bruger [b]index[/b] i stedet for [b]i[/b] for at undgå skrå tekst
for (test = P.back() + 2; test != 1; test+=2, root = sqrt(test)) {
	for (index = 1; P[index] <= root; index++)
		if(test % P[index]==0) {test+=2; root=sqrt(test); index=0;} // "index=0" idet FOR laver en index++ i næste loop
	if(test <= 0xFFFFFFFF) P.push_back(test);
	primes << P.back() << endl;
}

Med fare for at lyde utaknemmelig og respektløs...
Det virker ikke og giver iøvrigt ingen menning...

Suk! Utak er verdens løn
Nå, spøg til side:

Jeg har taget denne del af din kode

for (unsigned long long test = P.back() + 2; test != 1; test += 2) {
	root = sqrt(test);
	for (index = 0, is_prime = true; P[index] <= root && is_prime == true; i++)
		if (test % P[index] == 0)
			is_prime = false;
	if (is_prime == true && test <= 0xffffffff)
		P.push_back(test);
	if (is_prime == true)
		primes << P.back() << std::endl;
}

Og lavet den om til denne kode (der havde indsneget sig nogle fejl i de fremhævede dele)

for (test = P.back() + 2; true; test+=2, root = sqrt(test)) {
	for ([b]index = 0[/b]; P[index] <= root; index++)
		if(test % P[index]==0) {
			test += 2;
			root = sqrt(test);
			[b]index = -1;[/b]		// index øges til 0 i næste loop,
		}
	if(test <= 0xFFFFFFFF)
		P.push_back(test);
	primes << P.back() << endl;
}

Da du alligevel har en unsigned long long i kan du lige så godt flytte unsigned long long test samme sted hen. Det sparer lidt kode.

root=sqrt(test) kan lige så godt være i yderste FOR-loop, sparer en linie, men ellers intet.

Yderste FOR-loop: test!=1 kan lige så godt erstattes med true

Når test%p[index]==0) er sand, er meningen med prime=false, at næste tal skal testes. For ikke unødigt at gå ned til IF-sætningerne efter inderste løkke, udføres bare samme kode som is_prime==false ville have medført.

Efter min ændring vides nu med sikkerhed at if(is_prime==true) er sand efter inderste løkke, og derfor kan if(is_prime) helt fjernes.

Desværre ændrer det ikke væsentligt ved hastigheden, og det er på grund af to ting: 1) Måden du gemmer tal i filen. 2) Brugen af deque.
1) Primtallene gemmes i filen som tal der kan læses af mennesker. Så der skal en konvertering til, fra unsigned long long til char[], hver gang der gemmes, og det er noget der tager tid!
Jeg tvivler på, at du nogensinde får brug for, at læses indholdet af filen med dine egne øjne. Så det må være rigeligt at gemme primtallene som unsigned long long datatype. Det sparer iøvrigt plads når primtallene bliver meget store.
2) Når deque mangler plads, allokerer den mere plads. Om den så også kopierer alle de gamle data til den nye plads, er jeg ikke klar over, men hvis den gør..., puha en tidsrøver.
Det interessante er, at du ikke har behov for at have hurtig adgang til alle primtallene, da du kun bruger dem der er mindre end kvadratroden af test.

Jeg måtte lige prøve om det kunne lade sig gøre, at ændre ved disse to punkter og fandt frem til denne kode:

#include <iostream>
#include <fstream>
using namespace std;

static const long ARRAYSIZE = 1<<20;

// Denne union er nødvendig, da streams kun behandler char typer
union {
	__int64 value;
	char v[sizeof(__int64)];
} num;

void calc() {
	__int64 prime, test = 1, root2 = 1;
	__int32 index = 0, rootindex = 0, rootarray[65536], fileindex = 0, primecount = 1;
	fstream primes("primes.txt", ios::in | ios::out | ios::binary | ios::trunc);

	num.value = 2;
	primes.write(num.v, sizeof(__int64));
	while(primecount<ARRAYSIZE && rootindex<65536) {
		test+=2;
		if(test>=root2) {
			// Get next prime from primes
			primes.seekg(fileindex);
			primes.read(num.v, sizeof(__int64));
			fileindex = primes.tellp();
			primes.seekp(0, ios::end);
			rootarray[rootindex++] = num.value;
			root2 = num.value * num.value;
		}
		index = 0;
		while(true) {
			prime = rootarray[index++];
			if(!(test%prime)) // IS NOT prime
				break;
			if(index>=rootindex) { // IS prime
				num.value = test;
				primes.write(num.v, sizeof(__int64));
				primecount++;
				break;
			}
		}
	}
	// Write the contents of the file
	
	primes.seekg(0);
	primes.read(num.v, sizeof(__int64));
	while(primes.good()) {
		cout << (long double)num.value << endl;
		primes.read(num.v, sizeof(__int64));
	};
	cin.get();
	
	primes.close();
}

void main() {
	calc();
}

Min compiler gider ikke æde unsigned long long, så jeg bruger andre typer, men resultatet bør være det samme.
rootarray er jo ikke så stor, men med primtal nummer 65536 = 821.641 kan man teste tal helt op til 675.093.932.881