Hallo Leute
,
Ich hab ein Problem mit der Umsetzung eines
Algorithmus zur Bestimmung der Primalität einer Ganzahl.
kann mir Jemand helfen ? :
Code:
4 The Algorithm
Input: integer n > 1
1. if (n is of the form a^b, b>1) output COMPOSITE; // n ist das Ergebnis einer Exponierung
2. r = 2;
3. while(r<n) {
4. if (gcd(n,r) <>(nicht gleich) 1) output COMPOSITE; // gcd = größter gemeinsamer Teiler
5. if (r is prime)
6. let q be the largest prime factor of r
7. if (q >= (4 Sqrt(r) log n)) and (n((r-1)/q) <>(nicht deckungsgleich(kongruent)) 1(mod r))
8. break;
9. r = r + 1;
10. }
11. for a = 1 to (2 Sqrt(r) log n)
12. if ( ((x-a)^n) <>(nicht deckungsgleich(kongruent)) (((x^n)-a)(mod (x^r)-1, n)) ) output COMPOSITE;
13. output PRIME;
Theorem 4.1. The algorithm above returns PRIME if and only if n is prime.
Zusätzlich ist noch das dazugehörige PDF-File angehängt.
Den GCD hab ich schon umgesetzt, aber die Zeile 1 ist mein 1. Hauptproblem.
Dabei wird festgestellt, ob n das Ergebnis einer Exponierung (a^b) ist, wobei b > 1.
Nur hab ich keinen Plan, wie ich das Umsetzen kann.
Mathematik kann so schön sein ... wenn man sie versteht !
[edit=sakura] Titel geändert. Mfg, sakura[/edit]