stiehler.dev Marian Stiehler
Ein Primzahl-Algorithmus in Swift, Java, C++ und MMIX: iterativ, objektorientiert und rekursiv
Iterativ – objektorientiert – rekursiv: Gegenüberstellung von drei einfachen Implementierungen eines Algorithmus zur Bestimmung der ersten 500 Primzahlen.
Der folgende Algorithmus – hier implementiert in Swift, nur objektorientiert in Java, und, nur iterativ, in C++ – findet die ersten 500 Primzahlen. Es wird versucht, die Zahl (den »Kandidaten«) durch alle Primfaktoren, die kleiner als er und bereits gefunden worden sind, ganzzahlig ohne Rest zu teilen. Gelingt dies, ist die Zahl nicht prim. Gelingt dies nicht, ist die Zahl prim. Dabei werden nur ungerade Zahlen als Kandidaten berücksichtigt. 2 sei per Definition prim.
Wenn Sie ein Gerät mit kleinem Bildschirm verwenden, drehen Sie es für die Code-Abschnitte und die Grafik bitte ins Querformat.
Algorithmische Form
(orientiert an der Darstellung von Donald Knuth in The Art of Computer Programmming)
Algorithmus P (Gib Tabelle mit 500 Primzahlen aus.)
P1. [Starte Tabelle und Konstante.] Setze primes[0] ← 2, candidate ← 3, MAX_NUMBER_OF_PRIMES ← 500. (In den folgenden Schritten läuft candidate über die ungeraden Zahlen.)
P2. [MAX_NUMBER_OF_PRIMES gefunden?] Falls Länge von primes[] == MAX_NUMBER_OF_PRIMES, gehe zu Schritt P6.
P3. [candidate/primefactors] Teile candidate ganzzahlig durch alle Primfaktoren in primes[]; ist der Rest einer dieser Divisionen 0, gehe zu Schritt P5 (candidate ist nicht prim, versuche die nächste Zahl). Sind alle Primfaktoren durchlaufen, ohne dass Rest 0 auftrat, gehe zu P4 (candidate ist prim).
P4. [candidate ist prim.] Hänge primes[] candidate an.
P5. [Iteriere candidate.] Setze candidate ← candidate + 2. Gehe zu Schritt P2.
P6. [Gib Primzahlen aus.] Gib primes[] aus. ❙
Swift
Iterativ
Der Code ist sehr modern, was ich sehr angenehm finde.
Objektorientiert
Einen solchen Algorithmus objektorientiert zu implementieren, ist eigentlich keine gute Idee. Der Code ist länger und weniger übersichtlich. Mich persönlich ärgert es, wenn Objektorientierung eingesetzt wird, obwohl sie gar nicht sinnvoll ist. Hier soll es aber darum gehen, Programmierstile gegenüberzustellen
Rekursiv
Eine rekursive Ausführung bietet sich zwar bei dem Algorithmus, nicht aber in Swift an. Der Code ist länger und erheblich komplizierter für praktisch das gleiche Ergebnis. Haskell wäre dafür besser geeignet.
Ausgabe
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581]
Java
Objektorientiert
Ich bin Java-Anfänger. Der zugrundeliegende Algorithmus ist der gleiche – die Implementierung ist aber die eines Anfängers. Für Feedback bin ich dankbar.
C++ Iterativ
MMIX iterativ
MMIX ist ein 64-Bit-Modellcomputer (RISC) aus Donald Knuth’s The Art of Computer Programming. Ihn kann man mit einer hardwarenahen Assembler-Sprache programmieren. Die folgende Implementierung stammt von Knuth selbst, ist also als einzige dieser Implementierungen nicht von mir. Sie ist so geschrieben, dass möglichst viele Features von MMIX präsentiert werden. Sie entstammt Volume 1, Fascicle 1.
Ausgabe
First Five Hundred Primes
0002 0233 0547 0877 1229 1597 1993 2371 2749 3187
0003 0239 0557 0881 1231 1601 1997 2377 2753 3191
0005 0241 0563 0883 1237 1607 1999 2381 2767 3203
0007 0251 0569 0887 1249 1609 2003 2383 2777 3209
0011 0257 0571 0907 1259 1613 2011 2389 2789 3217
0013 0263 0577 0911 1277 1619 2017 2393 2791 3221
0017 0269 0587 0919 1279 1621 2027 2399 2797 3229
0019 0271 0593 0929 1283 1627 2029 2411 2801 3251
0023 0277 0599 0937 1289 1637 2039 2417 2803 3253
0029 0281 0601 0941 1291 1657 2053 2423 2819 3257
0031 0283 0607 0947 1297 1663 2063 2437 2833 3259
0037 0293 0613 0953 1301 1667 2069 2441 2837 3271
0041 0307 0617 0967 1303 1669 2081 2447 2843 3299
0043 0311 0619 0971 1307 1693 2083 2459 2851 3301
0047 0313 0631 0977 1319 1697 2087 2467 2857 3307
0053 0317 0641 0983 1321 1699 2089 2473 2861 3313
0059 0331 0643 0991 1327 1709 2099 2477 2879 3319
0061 0337 0647 0997 1361 1721 2111 2503 2887 3323
0067 0347 0653 1009 1367 1723 2113 2521 2897 3329
0071 0349 0659 1013 1373 1733 2129 2531 2903 3331
0073 0353 0661 1019 1381 1741 2131 2539 2909 3343
0079 0359 0673 1021 1399 1747 2137 2543 2917 3347
0083 0367 0677 1031 1409 1753 2141 2549 2927 3359
0089 0373 0683 1033 1423 1759 2143 2551 2939 3361
0097 0379 0691 1039 1427 1777 2153 2557 2953 3371
0101 0383 0701 1049 1429 1783 2161 2579 2957 3373
0103 0389 0709 1051 1433 1787 2179 2591 2963 3389
0107 0397 0719 1061 1439 1789 2203 2593 2969 3391
0109 0401 0727 1063 1447 1801 2207 2609 2971 3407
0113 0409 0733 1069 1451 1811 2213 2617 2999 3413
0127 0419 0739 1087 1453 1823 2221 2621 3001 3433
0131 0421 0743 1091 1459 1831 2237 2633 3011 3449
0137 0431 0751 1093 1471 1847 2239 2647 3019 3457
0139 0433 0757 1097 1481 1861 2243 2657 3023 3461
0149 0439 0761 1103 1483 1867 2251 2659 3037 3463
0151 0443 0769 1109 1487 1871 2267 2663 3041 3467
0157 0449 0773 1117 1489 1873 2269 2671 3049 3469
0163 0457 0787 1123 1493 1877 2273 2677 3061 3491
0167 0461 0797 1129 1499 1879 2281 2683 3067 3499
0173 0463 0809 1151 1511 1889 2287 2687 3079 3511
0179 0467 0811 1153 1523 1901 2293 2689 3083 3517
0181 0479 0821 1163 1531 1907 2297 2693 3089 3527
0191 0487 0823 1171 1543 1913 2309 2699 3109 3529
0193 0491 0827 1181 1549 1931 2311 2707 3119 3533
0197 0499 0829 1187 1553 1933 2333 2711 3121 3539
0199 0503 0839 1193 1559 1949 2339 2713 3137 3541
0211 0509 0853 1201 1567 1951 2341 2719 3163 3547
0223 0521 0857 1213 1571 1973 2347 2729 3167 3557
0227 0523 0859 1217 1579 1979 2351 2731 3169 3559
0229 0541 0863 1223 1583 1987 2357 2741 3181 3571