logo-small-small-high-res.png

Marian Stiehler

Student

Informatik
Philosophie Psychologie Kunstwissenschaft

Sechs einfache Primzahl-Algorithmen

Sechs einfache Primzahl-Algorithmen

Objektorientiert – iterativ – rekursiv: Gegenüberstellung von fünf einfachen Implementierungen eines Algorithmus zur Bestimmung aller Primzahlen in einem bestimmten Zahlenbereich.

Der folgende einfache Algorithmus – hier implementiert in C++, Swift und Java – überprüft die ersten 1.000 Zahlen darauf, ob sie prim sind. Er tut dies mit Gewalt: Es wird versucht, die Zahl (den »Kandidaten«) durch alle Zahlen, die kleiner als sie sind, ganzzahlig zu teilen. Gelingt dies, bricht er ab, denn dann ist die Zahl nicht prim. Dabei werden nur ungerade Zahlen als Kandidaten berücksichtigt. 1, 2 seien per Definition prim. 

C++: Iterativ

Die Variante in C++ ist mein persönlicher Favorit. Dank der Hardware-Nähe von C++ ist sie auch diejenige, die generell am schnellsten ausgeführt wird. Vergleichswerte siehe unten.

Für eine bessere Darstellung laden Sie bitte den Quelltext herunter. Wenn Sie ein Gerät mit kleinem Bildschirm verwenden, drehen Sie es bitte ins Querformat.

#include <iostream>
#include <vector>

using namespace std;

bool isPrime (const int candidate) {
    for (int i = 2; i<candidate; ++i) {
            if (candidate % i == 0) {
                return false;
            }
        }
        return true;
    
}

int main() {
    vector<int> primes;
    const int lower_limit = 3;
    const int upper_limit = 1000;
    
    // 1 and 2 are prime by definition
    primes.push_back(1);
    primes.push_back(2);
    
    // check all odd numbers between LOWER_LIMIT and UPPER_LIMIT
    for (int x = lower_limit; x <= upper_limit; x += 2) {
        if (isPrime(x)) {
            primes.push_back(x);
        }

    }

    // print results
    for (int i = 0; i < primes.size(); ++i) {
            cout << primes[i] <<", ";
    }
    
    return 0;
        
}

Ausgabe

1, 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,

 

Swift

Iterativ

Der Swift-Algorithmus fügt die Zahlen einem Array hinzu, das am Ende gedruckt wird. Der Code ist sehr modern, was ich sehr angenehm finde. Leider lässt Swifts Performance im Vergleich mit C++ etwas zu wünschen übrig.

Für eine bessere Darstellung laden Sie bitte den Quelltext herunter. Wenn Sie ein Gerät mit kleinem Bildschirm verwenden, drehen Sie es bitte ins Querformat.

// set 1 and 2 as the first primes
var primes: [Int] = [1, 2]
let LOWER_LIMIT: Int = 3
let UPPER_LIMIT: Int = 1_000


func isPrime(candidate: Int) -> Bool {
// determines, if a given number (candidate) is prime

	for i in 2..<candidate {
		if (candidate % i) == 0 {
			return false
		}
	}
	return true
}

// check all odd numbers between LOWER_LIMIT and UPPER_LIMIT
for x in stride(from: LOWER_LIMIT, to: UPPER_LIMIT, by: 2) {
	if isPrime(candidate:x) {
		primes.append(x)
	}

}

print("Primzahltest")
print("------------")
print("\(primes)")

Objektorientiert

import Foundation

struct Candidate {
    let number: Int             // to store the number
    var prime: Bool = true      // assume Candidate is prime
    
    init(number: Int) {
        self.number = number    // store the number
        
        for i in 2 ..< number { // check if can be divided through anything between 2 and (not including) itself
            if number % i == 0 {
                self.prime = false
                break
            }
        }
    }
}

let start = Date()

var lower_limit: Int = 4        // must be > 0
let upper_limit: Int = 10_000   // must be > 0

// check limits
if lower_limit < 0 || upper_limit < 0 { print("Limits can't be negative in this implementation. Aborting.") }
 else { // limits are ok

    var primes: [Int] = []
    
    switch lower_limit {
        case 1, 2:
            // handle exceptional cases 1 and 2; 2 is prime, 1 is not; start algorithm with 3
            lower_limit = 3
            primes.append(2)
        default:
            // ensure lower_limit is odd number (even numbers aren't prime)
            if lower_limit % 2 == 0 { lower_limit += 1 }
    }
    
    // reserve some capacity to speed up appends
    let capacity: Int = (upper_limit-lower_limit) / 100 * 20
    primes.reserveCapacity(capacity)

    for candidate: Int in stride(from: lower_limit, to: upper_limit, by: 2) {
        let tocheck = Candidate(number: candidate)
        if tocheck.prime { primes.append(tocheck.number) }
    }
    
    print("""
        Primzahltest
        ------------
        Zwischen \(lower_limit) und \(upper_limit) sind die folgenden Zahlen prim:
        
        \(primes)
        
        """)

}
let end = Date()

let seconds = end.timeIntervalSince(start)

print("fertig nach \(seconds) Sekunden")

Ausgabe

Primzahltest ------------ [1, 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]

Java

objektorientiert

Für eine bessere Darstellung laden Sie bitte den Quelltext herunter. Wenn Sie ein Gerät mit kleinem Bildschirm verwenden, drehen Sie es bitte ins Querformat.

public class Main {

    public static void main(String[] args) {

        // Greeting
        System.out.println("Primzahltest");
        System.out.println("------------");

        // define range of numbers to check
        int LOWER_LIMIT = 1;
        int UPPER_LIMIT = 1000;


        // check all odd numbers between 1 and (including) UPPER_LIMIT
        for (int candidate = LOWER_LIMIT; candidate <= UPPER_LIMIT; candidate = candidate + 2) {
            Candidate tocheck;
            tocheck = new Candidate(candidate);

            if (tocheck.prime) {
                System.out.println(candidate + " ist prim!");
            }
        }
    }


    private static class Candidate {
        private boolean prime;

        private Candidate(int candidate) {
            // assume number is prime
            this.prime = true;

            // check, if number can be divided without remainder by any number lower than itself
            // if so, number is not prime
            for (int i = 2; i < candidate; i++) {
                if (candidate % i == 0) {
                    this.prime = false;
                    break;
                }
            }

        }
    }
}

iterativ

Iterativ statt objektorientiert wird der Code sogar noch etwas kompakter. Download

public class Main {

    private static boolean isPrime(int candidate) {

        for (int i = 2; i < candidate; i++) {
            if (candidate % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        // Greeting
        System.out.println("Primzahltest");
        System.out.println("------------");

        // define range of numbers to check
        int LOWER_LIMIT = 1;
        int UPPER_LIMIT = 1000;

        for (int candidate = LOWER_LIMIT; candidate < UPPER_LIMIT; candidate = candidate + 2) {

            if (isPrime(candidate)) {
                System.out.println(candidate + " ist prim!");
            }
        }
    }
}

rekursiv

public class Main {

    private static boolean isPrime(int candidate) {
        return isPrime(candidate, candidate - 1);
    }

    private static boolean isPrime(int candidate, int divisor) {

        // 1 is prime by definition
        if (candidate == 1) {
            return true;
        }

        if (divisor == 1) {
            return true;
        } else if (candidate % divisor == 0) {
            return false;
        } else {
            return isPrime(candidate, divisor - 1);
        }
    }


    public static void main(String[] args) {
        // Greeting
        System.out.println("Primzahltest");
        System.out.println("------------");

        // define range of numbers to check
        int LOWER_LIMIT = 1;
        int UPPER_LIMIT = 1000;

        for (int candidate = LOWER_LIMIT; candidate < UPPER_LIMIT; candidate = candidate + 2) {

            if (isPrime(candidate)) {
                System.out.println(candidate + " ist prim!");
            }
        }


    }
}

Ausgabe

Die Ausgabe ist in allen drei Java-Fällen gleich. Ich kürze sie hier ab:

Primzahltest ------------ 1 ist prim! 3 ist prim! 5 ist prim! 7 ist prim! 11 ist prim! 13 ist prim! 17 ist prim! 19 ist prim! 23 ist prim! 29 ist prim! ... 953 ist prim! 967 ist prim! 971 ist prim! 977 ist prim! 983 ist prim! 991 ist prim! 997 ist prim!

Zeitbedarf

Die konkrete Zeit zur Ausführung dieser Algorithmen hängt vom verwendeten System ab. Zudem sind die hier verwendeten Algorithmen nicht exakt gleich – C++ und Swift speichern die Primzahlen für eine spätere Verwendung, Java gibt sie nur aus. Die Werte sind dennoch wie erwartet: C++ ist am schnellsten, Java ist fast gleichauf. Hier sind Messwerte für die ersten 120.000 Zahlen auf meinem System in Millisekunden:

Gutes Design und Heidegger

Gutes Design und Heidegger

Bitte schließt Eure Apps nicht!

Bitte schließt Eure Apps nicht!