Robert Eisele
Engineer, Systems Architect and DBA

Skillvalue: 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 most efficient 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;
}

« Back to problem overview