Generation of Prime Numbers

Question

I have created this prime number generator. I want it to be as fast as possible, but I am wondering if there is a faster way (there must be).

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

bool is_prime(const unsigned long long);

int
main(
    void)
{
    puts("2\n3");

    for (unsigned long long n = 5; n < ULLONG_MAX; n+=2) {
        if (is_prime(n)) {
            printf("%llu\n", n);
        }
    }
}

bool
is_prime(
    const unsigned long long n)
{
    if (n < 4) {
        return n > 1;
    } else if (n % 2 == 0 || n % 3 == 0) {
        return false;
    } else {
        for (unsigned long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }

        return true;
    }
}

Possible slow areas:

• usage of printf
• usage of bool instead of int (not sure)

Compilation command:

clang -O3 -Weverything -pipe -march=native -o png png.c

Answer 1

The prime reason your code is slow, is simply that you don't remember earlier calculation on what numbers are prime or not. So you recalculate it every time, for every number, and that is a lot of calculations.

Code review

Your code looks clean enough, and the style is good. I would consider having all of the arguments on the same line as long as you don't have too many arguments. But then again being consistent and writing code according to a defined style does make for clean and readable code.

Your choice of doing a for loop which adds 6 at a time (within is_prime) is wise, and rather useful to avoid doing too many tests when you want to display or check a lower number for primality. However this gets very expensive when you want to display all primes below a given \$n\$.

Implement a better algorithm

You should look into using other algorithms for generating prime numbers, and apply one of these. For some theory read Wikipedia: Prime number, and an article on one of the better approaches: Wikipedia: Sieve of Eratosthenes. Another article on the latter is Determine if a Number is Prime.

The base concept of "The Sieve of Eratosthenese" is to have an array of \$n\$ numbers with boolean values, and then you start crossing out all multiples of 2, continue with crossing out all multiples of 3, and then you continue finding the next in the array which isn't crossed out, and remove all multiples of that. In the end you have a list of all primes below \$n\$.

In your case you could output each prime at the start of crossing them out. But be warned that this algorithm does require a lot of space, and it will still take a substantial amount of time and memory to find all the primes below ULLONG_MAX.

A combined approach

Something which would give you some gain, but not a lot would be to build a temporary array of primes, and use this to eliminate most of the lower cases. I.e. if you have a table of the first 1000 primes, you can avoid checking higher number for all those not being in that list. Which would falsify higher candidate numbers somewhat sooner.

The flip side is that when you get to higher candidate numbers the primes are further apart, so it will get slow very fast, even with such a combined approach.

Answer 2

Neither printf() nor bool would cause a significant performance impact. One reason could be that you're looping through a huge number which, depending on the system, could be as low as 18446744073709551615. Doing so in serial would likely take a long time for such a range, and you can always consider adding parallelization where feasible.

Beyond that, any slowdown would be in is_prime(). Not only are there are a few conditionals, which could involve slowdown from branch prediction, but there's another loop that could take a while. You may consider looking for pre-existing prime algorithms elsewhere, which could be faster than yours. That should help improve runtime considerably.