Stuff

1: 0.000000
2: 0.000000
4: 0.250000
8: 0.500000
16: 0.625000
32: 0.656250
64: 0.640625
128: 0.609375
256: 0.578125
512: 0.550781
1024: 0.524414
2048: 0.494629
4096: 0.459473
8192: 0.420654
16384: 0.382507
32768: 0.349976
65536: 0.326782
131072: 0.314400
262144: 0.311932
524288: 0.316700
1048576: 0.325197
2097152: 0.334058
4194304: 0.340790
8388608: 0.344131
16777216: 0.344028
33554432: 0.341329
67108864: 0.337336
134217728: 0.333355
268435456: 0.330365

---

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef long long int uint64_t;

int p(uint64_t p) {
    // memoization table for primality
    static int *table = NULL, table_size = 0;
    int i, acc = 0;
    for (i = 0; p; i++) {
        if (p & 1)
            acc++;
        p >>= 1;
    }

    // 1 is not a prime
    if (acc == 1)
        return 0;

    // memoization table for primality of acc
    if (table_size < acc) {
        table = realloc(table, (acc + 1) * sizeof(int));
        for (i = table_size; i <= acc; i++)
            table[i] = 2;
        table_size = acc;
    } else {
        if (table[acc] != 2)
            return table[acc];
    }

    int sacc = sqrt(acc);

    for (i = 2; i <= sacc; i++) {
        if (!(acc % i))
            return table[acc] = 0;
    }

    return table[acc] = 1;
}

int prime_counter(void) {
    uint64_t i = 0, acc = 0, t = 1;

    while (++i) {
        if (p(i))
            acc++;
        if (i == t) {
            printf("%lld: %f\n", i, (double)acc / (double)i);
            t *= 2;
        }
    }
}