Effektiverer Primzahlenalgorithmus?

XFame schrieb:

Du koenntest auch versuchen, zwei Zahlen a und b zu finden fuer die Folgendes gilt: a^2 - b^2 = p .
p sei hier deine auf primalitaet zu testende Zahl.
Sollte p keine Primzahl sein, so hast du zwei nichttriviale Teiler gefunden, naemlich a-b und a+b.

Ist das so?

Sei p=3, a=2, b=1. -> Triviale Teilwer gefunden.

Ah, hab mich verlesen, sorry.

Taurin

Noch ein ganz einfacher Trick: Du kannst rund die Hälfte der Iterationen sparen, wenn du nur auf ungerade Teiler testest und die 2 gesondert behandelst.

if(value%2 == 0)
  //primzahl
else for(int i = 3; i <= sqrt(value); i += 2)
{
   //...
}

volkard

Taurin schrieb:

Noch ein ganz einfacher Trick: Du kannst rund die Hälfte der Iterationen sparen, wenn du nur auf ungerade Teiler testest und die 2 gesondert behandelst.
if(value%2 == 0)
  //primzahl
else for(int i = 3; i <= sqrt(value); i += 2)
{
   //...
}

warum machst du wieder i<=sqrt(value) statt i*i<=value?

was mir gerade so einfällt:

Die modulorechnung wird ja gebraucht , die lastet ja den prozessor sehr aus.
Es wird ja immer bei nem Primzahlalgorithmus auf zu testen % x == 0 geprüft.

Modulorechnung ist doch dazu da den divisionsrest zu bestimmen.

Nun stellt sich mir die frage ob es nicht eine ganz einfache viel schnellere rechenoperation ( oder kombination aus dessen ) gibt die nur zurückliefert ob ergebnis ohne oder mit nachkommastellen.

Schließlich weiß man bei einer Zahl wie 2342354353453459 das sie geteilt durch 45332342342 nur ein nachkommastelliges ergebnis liefert ohne bis zur 0 die ganze zahl von der anderen zu subtrahieren.

Ich bin der meinung dass es sicher irgendwie möglich ist so eine operation zu codieren die uns das problem erheblich schneller behebt.

rapso

volkard schrieb:

Taurin schrieb:
Noch ein ganz einfacher Trick: Du kannst rund die Hälfte der Iterationen sparen, wenn du nur auf ungerade Teiler testest und die 2 gesondert behandelst.
if(value%2 == 0)
  //primzahl
else for(int i = 3; i <= sqrt(value); i += 2)
{
   //...
}
warum machst du wieder i<=sqrt(value) statt i*i<=value?

weil i*i in jedem schleifendurchlauf gerechnet werden muss, während sqrt(value) vom kompiler eventuell nur einmal eingebaut wird.

rapso->greets();

volkard

rapso schrieb:

weil i*i in jedem schleifendurchlauf gerechnet werden muss, während sqrt(value) vom kompiler eventuell nur einmal eingebaut wird.

aber bei den meisten zahlen braucht manb nur ganz wenige tests, um sie als zusammengesetzt zu erkennen. wenn wir die zahlen bis 1000 betrachten, sind's nur 168 stück, die die volle ausmerksamkeit mit durchschnittlich unter 22 tests benötigen.
da sieht mir i*i aber schneller aus.

edit: nicht zu vergessen, daß quadrate ja auch nur summen von natürlichen zahlen sind. insbesondere ist n^2 gleich der summe der ersten n ungeraden zahlen. beweis zum beispiel durch (n+1)^2 = n^2 + 2*n+1 und vollständige induktion.

also schenkt man sich bei bedarf auch die multiplikation mit
int square=9;
for(int i = 3; i <= square; square+=1+i+=2 )

Aedyn

Dein ganz oben genannter Algorithmus ist doch eh sehr schnell!
Bei der Eingabe von "999999999" (9x die 9) geht die Berechnung so schnell wie bei einer "2".

Wo liegt das Problem?

Teste doch mal selber, ist sauschnell:

#include <iostream> 
using namespace std;

const bool isPrime (unsigned long value) 
{ 
        // 'value' muss größer als 1 sein. 
    if (value <= 1) return (false); 

        // Prüfung mit i=2 starten 
    for (register unsigned long i=2; i<value; ++i) 
    { 
        register const double         d = static_cast<double>(value)/i;  // Quotienten errechnen 
        register const unsigned long ud = static_cast<unsigned long>(d); // Nachkommastellen entfernen 

            // Wenn es einen Teiler gibt, ist die 'value' keine Primzahl 
        if (d == static_cast<double>(ud)) return (false); 
    } 

        // 'value' ist eine Primzahl 
    return (true); 
} 

void main()
{
	while(1)
	{
		unsigned long zahl;
		cout << "Zahl: " << endl;
		cin >> zahl;
		if(isPrime(zahl))
			cout << "Diese Zahl ist eine Primzahl!" << endl;
		else
			cout << "Diese Zahl ist keine Primzahl!" << endl;
	}
}

rapso

volkard schrieb:

rapso schrieb:

weil i*i in jedem schleifendurchlauf gerechnet werden muss, während sqrt(value) vom kompiler eventuell nur einmal eingebaut wird.

aber bei den meisten zahlen braucht manb nur ganz wenige tests, um sie als zusammengesetzt zu erkennen. wenn wir die zahlen bis 1000 betrachten, sind's nur 168 stück, die die volle ausmerksamkeit mit durchschnittlich unter 22 tests benötigen.
da sieht mir i*i aber schneller aus.

aufgrund der dependencies schaut es für mich langsammer aus. erst muss das ergebnis von i*i bereitstehen um dann den vergleich zu machen um dann den conditional jump.

anhand der angaben von AMD für den amd64:
imul 7 bzw 8cycles
fsqrt 35hz, also ca 5muls.
mit allem overhead dürfte ab ca 10*10 die wurzel schneller sein.

rapso->greets();

Jester

Scherzkeks. Die Zahl ist ja auch durch 3 teilbar und fliegt deswegen im zweiten Durchlauf der Schleife raus. Nimm mal ne sehr große Primzahl, da rechnet er schon ne Weile länger. Oder benutze das Programm mal um alle Primzahlen bis 1 Million zu finden. Daran sieht man gut, wie leistungsfähig (oder auch nicht) es ist.

volkard

rapso schrieb:

mit allem overhead dürfte ab ca 10*10 die wurzel schneller sein.
rapso->greets();

10*10?
je nach rest des codes. und der ist bestimmt nicht stabil.
wenn man vorher
if(kandidat%2==0) return kandidat==2;//sollte man tun
schreibt, wird sqrt besser.
mit noch nem
if(kandidat%2==0) return kandidat==2;//sollte man auch tun
erst recht.
naja, die 5 und die 7 können auch noch hardcoded getestet werden.
damit erwischt man bereits recht viele der zusammengesetzten zahlen und es ist unwahrscheinlich, überhaupt aus der schleife zu fliegen.

heißt fsqrt, daß er auf floats rechnet? hab ich da auch keine rundungsfehler, also gibt es zu jedem int eine eineindeutige fließkommzahl?