3. Sieb des Eratosthenes (Visualisierung)

Sieb des Eratosthenes (Visualisierung)

  • E

    Mir geht es um eine Visualisierung des Siebs des Eratosthenes, also das Aufzeigen des Streichens von Zahlen.
    http://www.primzahlen.de/primzahltests/sieb_des_eratosthenes.htm

    Ich habe mir folgende farbliche Darstellung in der Konsole überlegt:

    #define NOMINMAX     // due to conflict with max()
#include <windows.h> // warning: no C++ standard!
#include<iostream>
#include<chrono>
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

void wait()
{
	cout << "wait: Press any key to continue." << endl;
	cin.clear();
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();
}

void setConsole() // windows.h
{
	_CONSOLE_SCREEN_BUFFER_INFO info;
	HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
	GetConsoleScreenBufferInfo(handle, &info);
	COORD c;
	c.X = max<SHORT>(info.dwSize.X, 150);
	c.Y = max<SHORT>(info.dwSize.Y, 1000);
	SetConsoleScreenBufferSize(handle, c);

	SMALL_RECT RECT;
	RECT.Left = 0;
	RECT.Top = 0;
	RECT.Bottom = max(info.srWindow.Bottom - info.srWindow.Top, 40 - 1);
	RECT.Right = max(c.X - 1, 100 - 1);
	SetConsoleWindowInfo(handle, TRUE, &RECT);
}

void textcolor(unsigned short color = 15)  // windows.h
{
	SetConsoleTextAttribute(::GetStdHandle(STD_OUTPUT_HANDLE), color);
}

int main()
{
	setConsole();
	uint32_t primeLimit = 900;
	vector<bool> primes(primeLimit+1);
	uint32_t global_count = 0; // total number of primes

	chrono::time_point<chrono::system_clock> start, last; // for measuring execution time
	start = chrono::system_clock::now(); 

	// initialize the number array
	primes[0] = false;
	primes[1] = false;

	for (uint32_t i=2; i<=primeLimit; ++i)
	{
		primes[i] = true;
	}

	uint32_t iMax = (uint32_t)sqrt((double)primeLimit) + 1;

	// sieving loop
	for (uint32_t i=2; i<iMax; ++i)
	{
		if (primes[i])
		{
			textcolor(10);
			cout << endl << i << ": ";
			textcolor(15);

			for (uint32_t j=2*i; j<=primeLimit; j+=i)
			{
				if (j < iMax)
					textcolor(12);
				else
					textcolor(15);
				cout << j << " ";

				primes[j] = false;
			}
		}
	}

	uint64_t elapsedTime = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count();

	textcolor(14);
	cout << endl << endl << "Primes: ";
	for (uint32_t i=0; i<=primeLimit; ++i)
	{		
		if (primes[i])
		{
			global_count++; // count the number of primes
			cout << i << " ";
		}			
	}

	textcolor(15);
	cout << endl << endl << "In " << elapsedTime << " ms we found " << global_count << " prime numbers (2 to " << primeLimit << " )." << endl;
	wait();
}

    http://henkessoft.de/Sonstiges/SiebEratosthenes.png

    Die grünen Zahlen sind die beim Streichkonzert bis Wurzel aus n (hier: 900 ==> 30) verbleibenden Primzahlen. Die roten Zahlen sind die bis Wurzel aus n in einer Multiplikationsreihe (2,3,5,...) gestrichenen Zahlen. Die weißen zahlen sind die über Wurzel aus n gestrichenen Zahlen. Die resultierenden Primzahlen sind in gelb dargestellt.

    Man erkennt hier gut, dass viele Zahlen in den Multiplikationsreihen mehrfach gestrichen werden (Optimierungsmöglichkeit).

    0
  • Mod

    Erhard Henkes schrieb:

    Man erkennt hier gut, dass viele Zahlen in den Multiplikationsreihen mehrfach gestrichen werden (Optimierungsmöglichkeit).

    Also fangen wir beim Streichen doch einfach mal ganz dreist mit dem Quadrat einer Zahl als Anfangswert an. Alle kleineren Vielfachen sind ja logischerweise schon gestrichen worden. Und für N>2 gehen wir in Doppelschritten weiter, denn jedes zweite vielfache ist ein Vielfaches von 2. Für 3 wird's schon trickreicher, denn wir wissen zwar, dass der direkte Nachfolger des Quadrats einer Primzahl eine gerade Zahl ist, aber wir wissen nicht, ob dieser Wert durch 3 teilbar ist. Überhaupt werden die Regeln, wie viele Vielfach man dann überspringen darf, dann so langsam kompliziert, aber es gibt gleichzeitig immer weniger Vielfache, so dass sich komplizierte Regeln immer weniger lohnen. Für 2 bringt es sicherlich was, für 3 und größere Primzahlen müsste man es mal vergleichen.

    0
  • V

    SeppJ schrieb:

    dann so langsam kompliziert, aber es gibt gleichzeitig immer weniger Vielfache, so dass sich komplizierte Regeln immer weniger lohnen. Für 2 bringt es sicherlich was, für 3 und größere Primzahlen müsste man es mal vergleichen.

    Man könnte im kleinen Bereich nachschauen, was im großen Bereich zu streichen ist.

    0

  • Was ist da jetzt das konkrete Problem?

    0
  • E

    Bisher hatte ich noch keines, wollte lediglich den antiken Streichvorgang aber auch die weiteren Optimierungsmöglichkeiten des Original-Siebes aufzeigen. Dafür habe ich diese Konsolenanwendung mit verschiedenen Farben fabriziert. SeppJ und volkard kennen/suchen bereits weitere Geschwindigkeitssteigerungen. Mir geht es hier vor allem um die Didaktik bez. Original-Sieb.

    0

  • Also wenn es rein um Optimierung geht, dann sollte man doch erstmal Messungen auf dem konkreten System und dem angestrebten Primelimit machen. Ich wuerde vermuten das die Geschwindigkeit sobald das Array gross genug ist allein von der Schreibgeschwindigkeit im Speicher abhaengt. Dann waere es z.b. egal ob ich in 3er oder 6er Schritten iteriere und ob ich jetzt ein paar Werte spaeter anfange. Das Bitgefummel koennte auch genug Overhead haben, so das sich ab einer gewissen Laenge vorgefertigte Masken lohnen, wo man auf modernen Systemen dann ja 64 Werte auf einmal updaten kann. Evtl. lohnt sich sogar noch eine weitere Indirektion zwischenzuschalten um insgesamt weniger Werte in seinem Array ablegen zu müssen.

    0
Anmelden zum Antworten