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

#define SIZE  50000000
#define SIZE2 5000000

int isprime(int n) {
    if (n < 2) {
        return 0;
    }
    else if (n == 2) {
        return 1;
    }
    else if (n % 2 == 0) {
        return 0;
    }
    else {
        for (int i=3; i*i<=n; i+=2) {
            if (n%i==0) {
                return 0;
            }
        }
        return 1;
    }
}

void primesieve(int len, char* arr) {
    memset(arr, 1, len);

    if (len > 0) arr[0] = 0;
    if (len > 1) arr[1] = 0;

    for (int i=4; i<len; i+=2) {
        arr[i] = 0;
    }

    for (int i=3; i*i<=len; i+=2) {
        if (arr[i]) {
            for (int j=2*i; j<len; j+=i) {
                arr[j] = 0;
            }
        }
    }
}

int main(int argc, char** argv) {
    LARGE_INTEGER frequency, t1, t2;
    char *arr = malloc(SIZE);

    QueryPerformanceFrequency(&frequency);

    QueryPerformanceCounter(&t1);
    primesieve(SIZE, arr);
    QueryPerformanceCounter(&t2);

    printf("%f\n", (double)(t2.QuadPart-t1.QuadPart)/frequency.QuadPart);

    for (int i=0; i<1000; i++) {
        if (arr[i] != isprime(i)) {
            printf("error at %d\n", i);
        }
    }

    QueryPerformanceCounter(&t1);
    for (int i=0; i<SIZE2; i++) {
        int b = isprime(i);
    }
    QueryPerformanceCounter(&t2);

    printf("%f\n", (double)(t2.QuadPart-t1.QuadPart)/frequency.QuadPart);

    return 0;
}