ACM ICPC Praktikum

Kapitel 7: Zahlentheorie

Übersicht

• Primzahlen• Größter gemeinsamer Teiler• Kleinstes gemeinsames Vielfaches• Modulo Arithmetik

Primzahlen

Test, ob x eine Primzahl ist:• Teste alle Zahlen von 1 bis x• x ausreichend, da für jeden Teiler y von x

gilt, dass y ¢ z = x für ein z, und entweder y oder z höchstens x sein kann

Primfaktorisierung1. prime_factorization(long x)2. {3. long i; /* counter */4. long c; /* remaining product to factor */

5. c = x;6. while ((c % 2) == 0) {7. printf("%ld\n",2);8. c = c / 2;9. }10. i = 3;11. while (i <= (sqrt(c)+1)) {12. if ((c % i) == 0) {13. printf("%ld\n",i);14. c = c / i;15. }16. else17. i = i + 2;18. }19. if (c > 1) printf("%ld\n",c);20. }

Größter gemeinsamer Teiler

• Problem: gegeben Zahlen a und b, finde größte Zahl c, so dass c|a und c|b.

• c: ggT(a,b)• ggT(a,a) = ggT(a,0) = ggT(0,a) = a• a<b: ggT(a,b) = ggT(a, b mod a)

(b=k ¢ a + r, dann ggT(a,b) | r)• a>b: ggT(a,b) = ggT(a mod b, b)

Größter gemeinsamer Teiler

1. long gcd(long p, long q) /* compute gcd(p,q) */2. {3. if (q == 0) return(p);4. if (p == 0) return(q); 5. if (q > p) return(gcd(q % p,p));6. if (p > q) return(gcd(q, p % q));7. return(q); /* p=q */8. }

Größter gemeinsamer Teiler1. /* Find the gcd(p,q) and x,y such that p*x + q*y = gcd(p,q) */2. long gcd(long p, long q, long *x, long *y)3. {4. long x1,y1; /* previous coefficients */5. long g; /* value of gcd(p,q) */

6. if (q > p) return(gcd(q,p, &y, &x));7. if (q == 0) {8. *x = 1;9. *y = 0;10. return(p);11. }12. g = gcd(q, p%q, &x1, &y1);13.14. *x = y1;15. *y = (x1 - floor(p/q)*y1);16. return(g);17. }

Kleinstes gemeinsames Vielfaches

• Kleinstes gemeinsames Vielfaches von a und b: kgV(a,b) (englisch: lcm(a,b))

• Regel: a ¢ b = ggT(a,b) ¢ kgV(a,b)

Modulo Arithmetik

• Negative Zahlen:-x mod n = n-(x mod n)

• Addition:(x+y) mod n = ((x mod n) + (y mod n)) mod n

• Multiplikation:x ¢ y mod n = ((x mod n) ¢ (y mod n)) mod n

xy mod n = (x mod n)y mod n= [((x mod n)y1) mod n) ¢ ((x mod n)y2) mod n)] mod n mit y = y1 + y2

Anwendungen

• Finde letzte Ziffer einer großen Zahl(z.B. 2100)

• RSA Verschlüsselung• Kalenderberechnungen