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

#define N    2000000000L
#define LEN  30
#define SIZE 8

static int array[] = {1, 7, 11, 13, 17, 19, 23, 29};

/*
 * (30a+b)(30c+d) / 30
 */
size_t getPos(size_t a, int b, size_t c, int d)
{
    return (LEN * c + d) * a + b * c + b * d / LEN;
}

/*
 * (30a+b)(30c+d) % 30
 */
int getOffset(int b, int d)
{
    int mod = b * d % LEN;
    for (int i = 0; i < SIZE; ++i)
    {
        if (array[i] == mod) return i;
    }
    return -1;
}

void init(unsigned char *mark, size_t len)
{
    clock_t beg = clock();
    size_t tmp = (size_t) sqrt(len / LEN);

    for (size_t a = 0; a <= tmp; ++a)
    for (size_t b = 0; b < SIZE; ++b)
    {
        if (!a && !b) continue;     // 不对1做处理
        if (mark[a] & 1 << b) continue;

        for (size_t d = 0; d < SIZE; ++d)
        for (size_t c = 0; c <= len; ++c)
        {
            if (!c && !d) continue;     // 不对1做处理

            size_t pos = getPos(a, array[b], c, array[d]);
            if (pos >= len) break;

            mark[pos] |= 1 << getOffset(array[b], array[d]);
        }
    }
    printf("init runs %lf seconds\n", (double) (clock() - beg) / CLOCKS_PER_SEC);
}

void output(unsigned char *mark, size_t len)
{
    long long count = 3;
    clock_t beg = clock();

    printf("2 3 5 ");
    for (size_t a = 0; a < len; ++a)
    {
        for (size_t b = 0; b < SIZE; ++b)
        {
            if (!a && !b) continue;     // 不对1做处理
            if (mark[a] & 1 << b) continue;

            printf("%zu%c", a * LEN + array[b], "\n "[++count % 10 != 0]);
        }
    }
    printf("\nthere are %lld primes before %zu", count, len * LEN);
    printf("\noutput runs %lf seconds\n", (double) (clock() - beg) / CLOCKS_PER_SEC);
}

int main()
{
    size_t size = N / LEN + 1;

    unsigned char *mark = calloc(size, sizeof(char));

    fprintf(stdout, "will alloc %.3lf KB memory.\n", size / 1024.0);
    fprintf(stdout, "will alloc %.3lf MB memory.\n", size / 1024.0 / 1024);
    fprintf(stdout, "will alloc %.3lf GB memory.\n", size / 1024.0 / 1024 / 1024);
    if (!malloc_usable_size(mark))
    {
        fprintf(stderr, "can't alloc %.3lf MB memory.\n", size / 1024.0 / 1024);
        exit(EXIT_FAILURE);
    }

    init(mark, size);

    output(mark, size);

    free(mark);

    return 0;
}