Mein Primzahlprogramm

Ich hab im Netz mal einen Prime-Sieve basierenden Code gefunden:

Zeiten auf meinem Arbeitsrechner, AMD Athlon XP 3200+ (ist noch ein alter 32bitter), 1 GB RAM:
1 - 1.000.000: 0,219 Sek
1 - 10.000.000: 0,296 Sek
1 - 100.000.000: 1,156 Sek
1 - 1.000.000.000: 9,875 Sek

Der Code ist von Kim Walisch, ich finde im Moment den Link aber nicht mehr. Was schnelleres habe ich damals nicht gefunden...

Auf planet3dnow hat einer bis 4mrd in 1,5sec geschafft

Aber bestimmt nicht auf so einer lahmen Kröte wie meiner...

Ich hab den Link wiedergefunden: http://www.primzahlen.de/files/referent/kw/index.htm

walljumper

ne war ein Core2duo @3,2ghz trotzdem ist sein alg um einiges besser

Was ich erstaunlich find ist das mein code bis 1mio wesentlich schneller ist als deiner aber bei 10mio ist meiner viel langsamer.

hab jetzt bis 1mio 0,032sec
bis 10 mio ~2,2 sec

mein code wird nur langsam etwas unübersichtlich ^^ sollte da vieleicht mal aufräumen.

//---------------------------------------------------------------------------
#include<iostream>
#include<time.h>
#include<fastmath.h>
#pragma hdrstop
using namespace std;
//---------------------------------------------------------------------------
typedef unsigned int Int;
const Int lim=1000000;

int main()
{
double time1,time2,time3,time4;
time1=-clock();
// TEST ALGORITHMUS BEGIN
{
 bool *test = new bool[lim];
 for(Int i=0;i<lim;++i)
	test[i]=false;
 Int *Primes = new Int[lim];	

 Int firstborder = sqrt(lim);
 Int end;
 Int Zahl=1;
 Int stop;
 Int Prim=0;
 Int P2;
 Int tmp;
 Int start;
 bool isPrime;

 Primes[0]=2;

 while(Zahl<=firstborder)
	{
	Zahl+=2;
	if(test[Zahl]) continue;
	isPrime=true;
	stop = sqrt((float)Zahl);
	 for(Int i=0;Primes[i]<=stop;++i)
		{
			if(Zahl%Primes[i]==0)
				{
				isPrime=false;

				break;	
				}
		}
	 if(isPrime)
		{
		++Prim;
		Primes[Prim]=Zahl;
		end=lim/Zahl;
		for(Int i=2;i<end;++i)
			test[i*Zahl]=true;

		}
	}
	for(Int i=firstborder;i<lim;++i)
		{
			test[i]=true;
		}
 P2=Prim;
 time3=-clock();
 for(Int i=0;i<Prim;++i)
	{
		end=lim/Primes[i];
		start=firstborder/Primes[i];
		for(Int n=start;n<=end;++n)
			{
			tmp=n*Primes[i];
			test[tmp]=false;
			}
	}
	time4=clock();
 for(Int i=firstborder;i<lim;++i)
		{
			if(test[i]) ++P2;
		}
cout<<P2;
}
// TEST ALGORITHMUS END
time2 = clock();
cout<<endl<<(time1+time2)/CLOCKS_PER_SEC<<endl<<(time3+time4)/CLOCKS_PER_SEC;
getchar();
	return 0;
}

Gregor

Hmmm... in einem Primzahlenthread darf mein altes Primzahlzählprogramm nicht fehlen. ...in Java:

public class TestPrime
{
   public TestPrime ()
   {
   }

   public static void main (String[] args)
   {
      int end = 1000000000;
      long time = System.currentTimeMillis ();
      int [] sieve = new int [(end >> 5) + 1];
      int x, y, i;
      int primes = 1;
      int sqrt = (int)Math.sqrt((double)end);
      x = 3;
      while (x <= sqrt)
      {
         if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0)
         {
            y = x * x;
            i = x << 1;
            ++primes;
            while (end > y)
            {
               sieve[y >> 5] |= (0x1 << (y & 0x1f));
               y += i;
            }
         }
         x += 2;
      }
      while (x <= end)
      {
         if ((sieve[x >> 5] & (0x1 << (x & 0x1f))) == 0) ++primes;
         x += 2;
      }
      System.out.println ("Zwischen 0 und " + end +
                          " liegen " + primes + " Primzahlen.");
      System.out.println ("GesamtZeit : " +
                          (System.currentTimeMillis () - time) +
                           " Millisekunden");
   }
}

gregor@linux:~/JavaProjects/Test/TestPrime> /opt/jdk1.6.0/bin/java -Xmx192m TestPrime
Zwischen 0 und 1000000000 liegen 50847534 Primzahlen.
GesamtZeit : 41291 Millisekunden

Auf einem Pentium M mit 1,86GHz, 512MB RAM.

BTW: Bei den neuen Mehrkernprozessoren könnte man sich ja mal überlegen, ob man da irgendwie einen parallel arbeitenden Algorithmus schreiben kann.

EDIT: volkard hatte damals noch etwas deutlich schnelleres anzubieten. Vielleicht postet er seinen Code ja auch nochmal.