#include <print>
#include <bitset>

// Bereich der Primzahlen
constexpr int MAX = 100;

int main()
{
    // Bitset fuer Primzahlen
    // Ist ein Bit im Bitset 1, dann ist die entsprechende
    // Zahl eine Primzahl
    std::bitset<MAX> primes;

    // Alle Zahlen als Primzahlen markieren (auf '1' setzen)
    primes.set();
    // 0 und 1 sind keine Primzahlen!
    primes.reset(0);
    primes.reset(1);

    auto index = 2; // Start ist die Primzahl ist 2
    do
    {
        // Durchsuche alle Zahlen ab der aktuellen Primzahl+1
        // und entferne diejenigen, die durch die Primzahl teilbar sind
        for (auto prim = index+1; prim<MAX; prim++)
        {
            // Wenn Zahl noch als Primzahl markiert
            if (primes.test(prim))
            {
                // pruefe, ob Zahl durch Primzahl teilbar
                if (prim%index == 0)
                   // Wenn ja, dann ist Zahl keine Primzahl
                   primes.reset(prim);
            }
        }
        // Suche naechste noch als Primzahl markierte Zahl
        if (index++; index<MAX)
        {
            do
            {
                if (primes.test(index))
                   // nächste Primzahl gefunden
                   break;
                index++;
            } while (index<MAX);
        }
    } while (index<MAX);

    // Alle gefundenen Primzahlen ausgeben
    std::println("Gefundene Primzahlen:");
    for (auto lcount=0, index=0; index<MAX; index++)
    {
        // Wenn Primzahl gefunden
        if (primes.test(index))
        {
            std::print("{},", index);
            // Etwas Ausgabeformatierung
            lcount++;
            if ((lcount % 15) == 0)
                std::println("");
        }
    }
}
