3. Berechnung von Primzahlen

Berechnung von Primzahlen

  • C

    Jambe66 schrieb:

    was bedeuted das

    cout.flush();

    Das bewirkt, daß der Ausgabepuffer von cout ge"flush"t wird (die Ausgabe-Operatoren schreiben die Daten in einen Zwischenspeicher, der flush()-Befehl überträgt sie aus dem Zwischenspeicher auf den Monitor).

    und für was ist das l und das u in dieser funktio??

    int countprim(int l,int u)
{
  int ct=0;
  for(int i=l;i<=u;++i)
    if(isprim(i)) ct++;
  return ct;
}

    l = lower, u = upper - das ist die Unter- bzw. Obergrenze des Bereiches, in dem du nach Primzahlen suchst.
    (vielleicht solltest du dir die Funktionen auch mal ansehen, dann fallen dir solche Details auch auf ;))

    0
  • ?

    Jester schrieb:

    .Nunja, was heißt schneller. Du berechnest ja immer *alle* Primzahlen bis 30000. Auch wenn ich nur die bis 100 haben möchte.

    Du könntest übrigens noch ein paar Schleifendurchläufe sparen. Wenn Du Vielfache von 2 rausgeschmissen hast, ist es nicht mehr nötig auch die Vielfachen von 4 noch rauszuwerfen.

    Ja da hast du recht, wenn ich bloss prüfen soll ob ein Zahl wie 100 Prim ist, dann ist die Brute Force Methode schneller. Aber hier sollte ja ein ganzer Bereich abgedeckt werden und da is das Sieb des Eratosthenes schneller.

    Man könnte es sicherlich noch weiter optimieren indem man die Vielfachen von 2 vorher rausschmeisst und nur bis Wurzel(end) prüft.

    @CStoll
    Stimmt meine Funktion könnte übel abstürzen, wenn nicht genug Speicher für den Vector da ist. Danke für den Tip.

    0
  • ?

    justchris schrieb:

    Ja da hast du recht, wenn ich bloss prüfen soll ob ein Zahl wie 100 Prim ist, dann ist die Brute Force Methode schneller. Aber hier sollte ja ein ganzer Bereich abgedeckt werden und da is das Sieb des Eratosthenes schneller.

    Na ja, wenn ich sehe, dass die Siebfunktion, die ich im Netz gefunden hab, für alle Primzahlen zwischen 1 und 100.000.000 nur 1,156 Sekunden, respektive für alle zwischen 1 und 30.000 0,203 Sekunden benötigt, sehe ich gar keinen Grund eine Brute-Force Methode zu verwenden...

    0
  • J

    Eine nette Optimierung wäre zum Beispiel, das Sieb nur soweit zu berechnen, wie es auch benötigt wird.

    0
  • D

    Joe_M. schrieb:

    Na ja, wenn ich sehe, dass die Siebfunktion, die ich im Netz gefunden hab, für alle Primzahlen zwischen 1 und 100.000.000 nur 1,156 Sekunden, respektive für alle zwischen 1 und 30.000 0,203 Sekunden benötigt, sehe ich gar keinen Grund eine Brute-Force Methode zu verwenden...

    Kannste dir vielleicht mal posten? Hab das Sieb als Dll-Funktion geschrieben und brauche für alle Primzahlen < 70000 auf nem 3 GHz Pentium 36,11 Sekunden.

    0
  • ?

    Das Programm ist von Kim Walisch und gibt es inkl. Source hier: http://www.primzahlen.de

    /Edit: Ich hab hier nur ein Athlon XP3200+...

    0
  • ?

    Hab das Sieb als Dll-Funktion geschrieben und brauche für alle Primzahlen < 70000 auf nem 3 GHz Pentium 36,11 Sekunden.

    Hmmm. Hab eine eigene Funktion auf einem Athlon XP2400 laufen.
    Für alle Primzahlen < 70000 ungefähr 58 ms (Sprich Millisekunden).

    0
  • ?

    und für alle Primzahlen < 700000 ungefähr 1,5 sek.

    0
  • D

    Verdammt, irgendwas mach ich da wohl falsch.

    0
  • ?

    DarthZiu schrieb:

    Verdammt, irgendwas mach ich da wohl falsch.

    Hast du die Ausgabe der Zahlen in der Berechnung drinnen ?

    0
  • D

    Nein, dass würde die Berechnung ja extrem verlangsamen. Ich geb nur am Ende die größte Zahl aus.

    Das is der Code:

    bool *source = new bool(length);

for(int i=0; i<length; i++) {

	source[i] = true;
}

source[0] = false;
source[1] = false;

for(i=2; i<length; i++) {
	if(source[i] == true) {
		for(int j=i+1; j<length; j++) {
			if(j%i == 0)
				source[j] = false;
		}
	}
}

source[1] = true;

for(i=length; i>0; i--)
	if(source[i] == true)
	{
		printf("%d", i);
		return 0;
	}
    0
  • C

    Also wenn du alle Primzahlen berechnen willst, bist du mit Erastotenes besser aufgehoben, anstatt für jede Zahl neu zu testen, ob sie prim ist. Wenn du nur die Größte Primzahl unter x benötigst, versuch's mal so:

    int maxPrim(int x)
{
  for(;isPrim(x);--x);
  return x;
}
    0
  • ?

    Meine isprim Funktion ohne Sieb:

    bool isprim(int &zahl)
{
   if(zahl%2!=0)
   {
      for(int i=3;i<=sqrt(zahl);i+=2)
      {
         if(zahl%i==0)return false;
      }
   }
   else return false;
   return true;
}
    0
  • ?

    crayathome schrieb:

    und für alle Primzahlen < 700000 ungefähr 1,5 sek.

    Auf die Gefahr hin, mich zu wiederholen: Für alle Primzahlen zwischen 1 und 100 Millionen: 1,156 Sekunden.
    Die Zeit für die Primzahlen zwischen 1 und 70000: 0,203 Sekunden. Das ist zwar deutlich langsamer, als Deiner, aber der Mensch merkt keinen Unterschied zwischen 58 ms und 203 ms. Zwischen 1 Sekunde und 15 Sekunden schon (oder wie lange braucht Dein Algo für die Primzahlen < 100.000.000? ).

    0
  • ?

    Ich weiss, das Sieb des Erastotenes wesentlich schneller ist.
    Nur ich konnte seine 36,11 Sekunden nicht nachvollziehen.

    0
  • D

    Mein Algorithmus ist aber das Sieb des Erastosthenes. Und ich denke eigentlich, dass ich es ohne großen Overhead geschrieben habe. Deswegen versteh ich nicht, wie man auf diese Zeitdifferenzen kommt...

    0
  • ?

    Ich hoffe, ich begehe keine Copyright-Verletzung:

    Das ist nicht das komplette Projekt, sondern nur die Unit mit dem Sieb!

    prim.h:

    #ifndef __prim_h
#define __prim_h

#include "integer.h"
#include "status.h"
#include "print.h"

#include <vector>

typedef 	std::vector<INTEGER>                    VECT;
typedef 	std::vector<INTEGER>::const_iterator    ITER;

class Prim
{
private:

bool PRINT;
bool STATE;

INTEGER start;
INTEGER stop;
INTEGER oldpr;
INTEGER prims;
INTEGER twins;
INTEGER *lprim;
INTEGER *dis;

VECT mem;

Status status;
Print print;

void SetArrays();
void LittlePrims();
void Sieve();
inline void isPrim(INTEGER);
void GetPrimNr();
void Help();

INTEGER GetFirstPos(INTEGER, INTEGER);

public:

Prim(int, char**);
Prim() : lprim(NULL) {}

void SearchPrims(INTEGER, INTEGER);

INTEGER GetPrims() {return prims;}
INTEGER GetTwins() {return twins;}
};

#endif

    prim.cpp:

    #include "prim.h"

#include <iostream.h> 
#include <math.h>
#include <stdlib.h>
#include <cstring>

#define INTSQRT(x)	(INTEGER) ceil(sqrt(x))
#define POSITION	(*d != 0) ?*d :GetFirstPos(*p, field)

//---------------------------------------------------------------------------
Prim::Prim(int argc, char** argv) : lprim(NULL)
{
for(int i = 1; i < argc; i++)
	{
	if(strcmp(argv[i], "-?") == 0) this->Help();

	if(strcmp(argv[i], "-sap") == 0) print.SetSaveP();
	if(strcmp(argv[i], "-shp") == 0) print.SetShowP();
	if(strcmp(argv[i], "-sat") == 0) print.SetSaveT();
	if(strcmp(argv[i], "-sht") == 0) print.SetShowT();
	}
}
//---------------------------------------------------------------------------
void Prim::SearchPrims(INTEGER pStart, INTEGER pStop)
{
start = (pStart > 1) ?pStart: 2;
stop  =  pStop  + 1;

STATE = print.bShow();
PRINT = print.bActive();

prims = 0;
twins = 0;
oldpr = 1;

status.Initialize(start, stop);
status.StartTime();

this->LittlePrims();
this->SetArrays();
this->Sieve();
this->GetPrimNr();

status.StopTime();
status.GetTime();
}
//---------------------------------------------------------------------------
void Prim::SetArrays()
{
if(lprim != NULL) delete lprim;

lprim = new INTEGER[mem.size()];
dis   = new INTEGER[mem.size()];

for(INTEGER i = 0; i < mem.size(); i++)
	{
	lprim[i] = mem[i];
	dis  [i] = 0;
	}

mem.clear();
}
//---------------------------------------------------------------------------
INTEGER Prim::GetFirstPos(INTEGER x, INTEGER y)
{
INTEGER i = (x - y % x) % x;
INTEGER j = (y + i) % 2;

return (j != 0) ?i :i + x;
}
//---------------------------------------------------------------------------
inline void Prim::isPrim(INTEGER n)
{
if(PRINT) print.Prime(n);
prims++;

if(n - oldpr == 2)
	{
	if(PRINT) print.Twin(n);
	twins++;
	}

oldpr = n;
}
//---------------------------------------------------------------------------
void Prim::LittlePrims()
{
INTEGER x = INTSQRT(stop);
INTEGER y = INTSQRT(x);

if(start <= 2 && x >= 2) isPrim(2);
if(start <= 3 && x >= 3) isPrim(3);

mem.push_back(3);
mem.push_back(stop);

ITER p;

for(INTEGER n = 5, s; n <= x; n += 2)
	{
	s = INTSQRT(n);
	p = mem.begin();

	while(*p <= s)
		{
		if(n % *p == 0) break;

		p++;
		}

	if(*p <= s) continue;

	mem.insert(mem.end() - 1, n);

	if(n <= y && y > start) isPrim(n);
	}
}
//---------------------------------------------------------------------------
void Prim::Sieve()
{
INTEGER incr  = INTSQRT(stop);
INTEGER field = start;

INTEGER i;
INTEGER j;
INTEGER *p;
INTEGER *d;
INTEGER SQRT;

bool *flags = new bool[incr];
bool *f	    = flags;
bool again  = true;

for(i = 0; i < incr; i++) *f++ = true;

while(again)
	{
	//--------------------------------------------

	i = field + incr;

	if(i < stop) SQRT = INTSQRT(i);
	else
		{
		SQRT  = INTSQRT(stop);
		incr  = stop - field;
		field = stop - incr;
		again = false;
		}

	//--------------------------------------------

	for(p = lprim, d = dis; *p <= SQRT; p++, d++)
		{
		i = POSITION;
		f = flags + i;

		j = *p + *p;

		while(i < incr)
			{
			if(*f) *f = false;

			f += j;
			i += j;
			}

		*d = i - incr;
		}

	//--------------------------------------------

	i = ~field & 1;
	f =  flags + i;

	while(i < incr)
		{
		if(!*f)	*f = true; else isPrim(field + i);

		f += 2;
		i += 2;
		}

	//--------------------------------------------

	field += incr;

	if(STATE) status.GetStatus(field);
	}
}
//---------------------------------------------------------------------------
void Prim::Help()
{
cout << "Prim - Version 4.0, Copyright (c) Kim Walisch 2002\n\n";

cout << "Parameter:\n\n";

cout << "  -?    zeigt die Hilfe an.\n";
cout << "  -shp  zeigt die Primzahlen auf dem Bildschirm an.\n";
cout << "  -sht  zeigt die Primzahlzwillinge auf dem Bildschirm an.\n";
cout << "  -sap  speichert die Primzahlen in eine Text-Datei.\n";
cout << "  -sat  speichert die Primzahlzwillinge in eine Text-Datei.\n\n";

cout << "mailto: kim_walisch@gmx.net";

exit(1);
}
//---------------------------------------------------------------------------
void Prim::GetPrimNr()
{
cout << "\a\n";
cout << "\nAnzahl der gefundenen Primzahlen:        " << prims;
cout << "\nAnzahl der gefundenen Primzahlzwillinge: " << twins;
}
//---------------------------------------------------------------------------
    0
  • ?

    Hier etwas, das zwar leider nicht so schön optimiert, dafür aber übersichtlicher und direkt lauffähig ist:

    #include <iostream>
#include <ctime>

typedef unsigned long ulong;

class SiebDesEratosthenes
{
public:
    SiebDesEratosthenes(ulong groesse) :
            m_groesse(groesse),
            m_sieb(new bool[groesse]),
            m_primAnzahl(groesse)
    {
        machSieb();
    }

    ~SiebDesEratosthenes() { delete [] m_sieb; }

    inline ulong primAnzahl() const { return m_primAnzahl; }
    inline ulong groesse() const { return m_groesse; }

    inline void schreibePrimzahlen(std::ostream &out) const
    {
        for(ulong i = 0; i < m_groesse; ++i)
            if(m_sieb[i])
                out << i << "\n";
        out.flush();
    }

    inline ulong groesstePrimzahl() const
    {
        for(ulong i = m_groesse-1; i >= 0; --i)
            if(m_sieb[i])
                return i;
        return 0;
    }

private:
    ulong m_groesse;
    bool *m_sieb;
    ulong m_primAnzahl;

    void machSieb()
    {
        ulong i;

        if(m_groesse<4)
        {
            for(i = 0; i < m_groesse; ++i)
                if( !(m_sieb[i] = (i > 1)) )
                    --m_primAnzahl;
            return;
        }

        m_sieb[0] = m_sieb[1] = false;
        m_sieb[2] = m_sieb[3] = true;
        m_primAnzahl -= 2;

        for (i = 4; i < m_groesse-1; i += 2)
        {
            m_sieb[i] = false;
            m_sieb[i + 1] = true;
            --m_primAnzahl;
        }

        if(m_groesse % 2)
        {
            m_sieb[m_groesse-1] = false;
            --m_primAnzahl;
        }

        for (i = 3; i*i < m_groesse; i += 2)
            if (m_sieb[i])
                for (ulong j = i*i; j < m_groesse; j += (2*i))
                    if(m_sieb[j])
                    {
                        m_sieb[j] = false;
                        --m_primAnzahl;
                    }
    }
};

int main()
{
    ulong zeit = time(0);
    SiebDesEratosthenes sieb(100000000);
    zeit = time(0) - zeit;
    std::cout << "Zwischen " << zeit << " und " << (zeit+1) << " Sekunden" << std::endl;
    std::cout << sieb.primAnzahl() << " Primzahlen unter 100 Millionen!" << std::endl;
    std::cout << "Die groesste ist " << sieb.groesstePrimzahl() << std::endl;
}
    0
  • C

    DarthZiu schrieb:

    Mein Algorithmus ist aber das Sieb des Erastosthenes. Und ich denke eigentlich, dass ich es ohne großen Overhead geschrieben habe. Deswegen versteh ich nicht, wie man auf diese Zeitdifferenzen kommt...

    Ganz einfach, du hast es sehr ineffizient implementiert - versuch's mal mit folgender Abwandlung:

    for(i=2; i<length; i++)
  if(source[i] == true)
    for(int j=2*i; j<length; j+=i)
      source[j] = false;
    0
Anmelden zum Antworten