#include <stdio.h>
#include <malloc.h>
#include <stdint.h>
#include <time.h>
#include <pthread.h>

#define buf_size_in_k_ints 4096
#define seg_size_in_k_ints 256

#define intbits uint32_t
intbits w;
intbits l;
intbits *a;
intbits bl;
intbits pos;

void *thread_func(void *ptr) {
        intbits *buf = malloc(bl*sizeof(intbits));
	intbits i = 1;

	for (intbits i = 2; i < bl; i++) {
		intbits beg = pos - (pos % i);
		buf[i] = beg + i;
        }
        intbits e =  pos -w + 1;
        intbits k = 0;
        for (k = (l/w)/2; k < l/w; k++) {
                e += w;
                for (intbits j = 2; j < bl; j++) {
                        for (i = buf[j]; i < e; i+=j) {
                                a[i]+=j;
                        }
                        buf[j]=i;
                }
        }
	return 0;
}

int main() {
	uint64_t cnt = 0;
	pthread_t tid;

	w = 1024 * seg_size_in_k_ints;
	l = w * 1024 / seg_size_in_k_ints * 10 * 13;
	a = malloc(l*sizeof(intbits));
	
	bl = buf_size_in_k_ints * 1024 + 1;
	intbits *b = malloc(bl*sizeof(intbits));

	pos = l/2;
	printf("seg_size_in_k_ints=%d, buf_size_in_k_ints=%d\n",seg_size_in_k_ints,buf_size_in_k_ints);
	printf("seg_size in bytes=%li\n", w*sizeof(intbits));
	printf("buffersize in bytes=%li\n", bl*sizeof(intbits));

	intbits i = 1;
	for (i = 1; i < l; i++) {
		a[i]=1;
	}
	intbits j = 2;
	/*
	for (j = 2; j < l/2; j++) {
		for (i = j*2; i < l; i+=j) {
			a[i]+=j;
		}
	}
	*/
	
	for (j = bl; j < l/2; j++) {
		for (i = j*2; i < l; i+=j) {
			a[i]+=j;
		}
	}

	pthread_create( &tid, NULL, thread_func, NULL );
	//clock_t begin = clock();
	for (i = 2; i < bl; i++) {
		b[i] = i * 2;
	}
	intbits e = 1;
	intbits k = 0;
	for (k = 0; k < (l/w)/2; k++) {
		e += w;
		if (e > pos + 1)
			break;
		for (j = 2; j < bl; j++) {
			for (i = b[j]; i < e; i+=j) {
				a[i]+=j;
				cnt++;
			}
			b[j]=i;
		}
	}
	//clock_t end = clock();
	pthread_join(tid, NULL);
	
	intbits c = 0;
	for (i = 1; i < l; i++) {
		if (a[i] < i) {
			if (a[a[i]] == i) {
				c++;
				printf("\n%d<=>%d",a[i],i);
			}
		}
	}
	printf("\npairs total = %d\n",c);
	/*double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("cnt:%li ", cnt);
        printf("time Taken:%F secs, time per work is %F\n", time_spent, time_spent/cnt*1000000);
	*/
	return 0;
}