Primality test benchmark

is_prime.c

#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>

bool is_prime(int n)
{
    if (n < 2)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int d = 6; d <= sqrt(n) + 1; d += 6)
        if (n % (d - 1) == 0 || n % (d + 1) == 0)
            return false;
    return true;
}

bool is_prime_sqrt_before_loop(int n)
{
    if (n < 2)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    double s = sqrt(n);
    for (int d = 6; d <= s + 1; d += 6)
        if (n % (d - 1) == 0 || n % (d + 1) == 0)
            return false;
    return true;
}

bool is_prime_n_const(const int n)
{
    if (n < 2)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int d = 6; d <= sqrt(n) + 1; d += 6)
        if (n % (d - 1) == 0 || n % (d + 1) == 0)
            return false;
    return true;
}

bool is_prime_d_times_d(const int n)
{
    if (n < 2)
        return false;
    if (n == 2 || n == 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int d = 6; d * d <= n + 1; d += 6)
        if (n % (d - 1) == 0 || n % (d + 1) == 0)
            return false;
    return true;
}

int main(void)
{
    struct timespec start, end;
    size_t n = 100'000'000;
    size_t prime_count = 0;
    clock_gettime(CLOCK_MONOTONIC, &start);
    for (int i = 0; i < n; i++)
    {
        if (is_prime(i))
        {
            // printf("%d\n", i);
            prime_count++;
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("Got %zu primes under %zu\n", prime_count, n);

    time_t delta_seconds = end.tv_sec - start.tv_sec;
    long long int delta_ns = end.tv_nsec - start.tv_nsec;
    if (delta_ns < 0)
    {
        delta_seconds -= 1;
        delta_ns += 1000000000;
    }
    printf("took: %zus %lldms\n", delta_seconds, delta_ns / 1'000'000);
    return 0;
}

result.txt

# Original
❯ gcc -lm -std=c23 -O3 t.c && ./a.out
Got 5761455 primes under 100000000
took: 19s 296ms

# Square root above loop
~/git/vids/prime master*
❯ gcc -lm -std=c23 -O3 t.c && ./a.out
Got 5761455 primes under 100000000
took: 19s 294ms

# D times D (result is slightly wrong but the scale of computation is the same)
~/git/vids/prime master*
❯ gcc -lm -std=c23 -O3 t.c && ./a.out
Got 5762071 primes under 100000000
took: 19s 260ms

# N is const
~/git/vids/prime master*
❯ gcc -lm -std=c23 -O3 t.c && ./a.out
Got 5761455 primes under 100000000
took: 19s 281ms