Skillvalue Solution: Smaller Primes

Determine all the prime numbers smaller than a given input value.

Input: N integer > 0

Output: the array with the prime numbers.

Example: for N = 10

Input: 10

The output is: 2 3 5 7

Solution

The easiest way to solve this task is probably using the Sieve of Eratosthenes to generate an array of primes and sum over all number that remain true in the sieve. Here is a small finger exercise in C++:

#include <iostream>
#include <fstream>

int main(int argc, char **argv) {
    unsigned int N;
    int c = 0;

    std::ifstream fs;
    fs.open(argv[1]);
    fs >> N;

    bool *A = new bool[N];

    for (int i = 2; i < N; i++) {
        A[i] = true;
    }

    for (int i = 2; i * i < N; i++) {
        if (A[i]) {
            for (int j = i * i; j < N; j += i) {
                A[j] = false;
            }
        }
    }

    for (int i = 2; i < N; i++) {
        if (!A[i]) continue;

        if (c > 0) {
            std::cout << " ";
        }
        c++;
        std::cout << i;
    }
    std::cout << std::endl;
    delete A;
    return 0;
}