#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>

// Suppose you want to find all prime numbers less
// than or equal to a given integer n.
//
// One way to do this is the Sieve of Eratosthenes:
//
// https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
//
// Implement a function that uses this algorithm
// to return a dynamically allocated array of
// all prime numbers less than or equal to n.
//
// There is one complication: we do not know how
// many prime numbers will be found.
//
// A function can return a pointer to an array,
// but the pointer alone does not tell us how
// many entries the array contains.
//
// There are two possible solutions:
//
// 1. Return a pointer to an array containing
//    all m prime numbers, followed by one
//    additional entry containing zero.
//
//    Since zero is not prime, it can indicate
//    the end of the array.
//
// 2. Return a pointer to the array and use a
//    pass-by-reference parameter to return the
//    number of prime numbers found.
//
// Later in the course, we will introduce classes
// that allow us to package an array and its size
// together.
//
// For now, implement the first solution.
//
// This is similar to a C-style string, which
// uses the null character '\0' to indicate
// the end of the string.
//
// Here, we will use the integer 0 to indicate
// the end of the array.
//
// For example, prime_array(10) should return
// an array containing
//
//     2, 3, 5, 7, 0
//
// The caller is responsible for releasing the
// dynamically allocated array using delete[].
//
// If n is less than 2, the returned array
// should contain only the terminating zero.

// Function declarations
unsigned long *prime_array(
    unsigned long const n
);

int main();

// Function definitions
int main() {
    unsigned long *a_primes{
        prime_array( 1000 )
    };

    // The first prime number must be 2.
    assert( a_primes[0] == 2 );

    // The last few primes not exceeding 1000 are
    // 953, 967, 971, 977, 983, 991, and 997.

    std::cout << a_primes[0];

    for ( std::size_t k{ 1 };
          a_primes[k] != 0;
          ++k ) {
        std::cout << ", " << a_primes[k];
    }

    std::cout << std::endl;

    // The array was dynamically allocated by
    // prime_array(...), so the caller must
    // release it when it is no longer needed.

    delete[] a_primes;
    a_primes = nullptr;

    // Test the cases where no primes exist.

    a_primes = prime_array( 0 );
    assert( a_primes[0] == 0 );
    delete[] a_primes;

    a_primes = prime_array( 1 );
    assert( a_primes[0] == 0 );
    delete[] a_primes;

    a_primes = nullptr;

    return 0;
}

unsigned long *prime_array(
    unsigned long const n
) {
    // Enter your implementation here.

    return nullptr;
}




























// Hint:
//
// First, dynamically allocate a Boolean array
// with n + 1 entries:
//
//     bool *a_is_prime{ new bool[n + 1]{} };
//
// The empty braces initialize every entry
// to false.
//
// Set the entries from 2 through n to true.
//
// Apply the Sieve of Eratosthenes to mark
// composite numbers as false.
//
// Count how many entries remain true.
//
// Allocate another array with one more entry
// than the number of primes:
//
//     unsigned long *a_primes{
//         new unsigned long[prime_count + 1]
//     };
//
// Copy the prime numbers into this array
// in increasing order.
//
// Set the final entry to zero.
//
// Remember to release the temporary Boolean
// array before returning the prime array.










































// Here is one solution:

/*
unsigned long *prime_array(
    unsigned long const n
) {
    // If n is less than 2, there are no
    // prime numbers to return.

    if ( n < 2 ) {
        return new unsigned long[1]{ 0 };
    }

    // Ensure that n + 1 can be represented
    // by unsigned long.

    assert(
        n < std::numeric_limits<unsigned long>::max()
    );

    // Allocate and initialize the sieve.
    // Every entry is initially false.

    bool *a_is_prime{ new bool[n + 1]{} };

    // Initially assume every integer from
    // 2 through n is prime.

    for ( unsigned long k{ 2 }; k <= n; ++k ) {
        a_is_prime[k] = true;
    }

    // Apply the Sieve of Eratosthenes.
    //
    // If p is prime, mark its multiples
    // p*p, p*p + p, p*p + 2*p, ...
    // as composite.
    //
    // Use p <= n/p instead of p*p <= n
    // to avoid overflow in the condition.

    for ( unsigned long p{ 2 }; p <= n/p; ++p ) {
        if ( a_is_prime[p] ) {
            for ( unsigned long multiple{ p*p };
                  multiple <= n; ) {
                a_is_prime[multiple] = false;

                // Stop before the next addition
                // could exceed n or overflow.

                if ( p > n - multiple ) {
                    break;
                }

                multiple += p;
            }
        }
    }

    // Count the prime numbers.

    std::size_t prime_count{ 0 };

    for ( unsigned long k{ 2 }; k <= n; ++k ) {
        if ( a_is_prime[k] ) {
            ++prime_count;
        }
    }

    // Allocate space for every prime number
    // and one additional terminating zero.

    unsigned long *a_primes{
        new unsigned long[prime_count + 1]
    };

    // Copy the prime numbers into the new array.

    std::size_t prime_index{ 0 };

    for ( unsigned long k{ 2 }; k <= n; ++k ) {
        if ( a_is_prime[k] ) {
            a_primes[prime_index] = k;
            ++prime_index;
        }
    }

    assert( prime_index == prime_count );

    // Terminate the array with zero.

    a_primes[prime_count] = 0;

    // The temporary sieve is no longer needed.

    delete[] a_is_prime;
    a_is_prime = nullptr;

    return a_primes;
}
*/