#include <vector>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

class PrimeTable
{
private:
    std::vector<bool> m_primes;
    unsigned int      m_maxIndex;

public:
    PrimeTable (unsigned int maxIndex);

    bool isPrime (unsigned int p) const;
    unsigned int findPrimeNear (unsigned int i) const;
    unsigned int maxIndex() const;
};

PrimeTable::PrimeTable (unsigned int maxIndex) :
    m_primes (maxIndex + 1, true),
    m_maxIndex (maxIndex)
{
    assert (maxIndex >= 2);

    m_primes[0] = false;
    m_primes[1] = false;

    // Sieve of Eratosthens
    for (unsigned int p = 2; p <= maxIndex; p++)
    {
        if (m_primes[p])        // p is a prime number
        {
            for (unsigned int no_p = p * 2; no_p <= maxIndex; no_p += p)
            {
                // no_p can be divided by p => is not a prime number
                m_primes[no_p] = false;    
            }
        }
    }
}

bool PrimeTable::isPrime (unsigned int p) const
{
    assert (p <= m_maxIndex);

    return m_primes[p];
}

unsigned int PrimeTable::findPrimeNear (unsigned int i) const
{
    assert (i <= m_maxIndex);

    if (i < 2)
        i = 2;

    while (!m_primes[i])
        i--;

    return i;
}

unsigned int PrimeTable::maxIndex() const
{
    return m_maxIndex;
}

int main()
{
    PrimeTable primeTable (100);

    srand (time (NULL));

    for (unsigned int i = 0; i <= primeTable.maxIndex(); i++)
    {
        if (primeTable.isPrime (i))
            printf ("%d\n", i);
    }

    for (unsigned int i = 0; i < 10; i++)
    {
        unsigned int z = rand() % (primeTable.maxIndex() + 1);
        printf ("Eine Primzahl nahe %d ist %d\n", z, primeTable.findPrimeNear (z));
    }
    return 0;
}