c program

prints prime numbers

How can I make this run faster and work for numbers ./a.out -u 1000000 and larger

#include #include #include #include #include #include #include

// must use mutex in struct typedef struct BitBlock_s { uint32_t *bits; pthread_mutex_t mutex; } BitBlock_t;

static uint32_t val = 10240; static BitBlock_t b; static int block_num = 320; static int num_threads = 1;

void setbit (BitBlock_t a, uint32_t k) { atomic_fetch_or(&a.bits[k/32], 1 << (k%32)); }

void clearbit (BitBlock_t a, uint32_t k) { atomic_fetch_and(&a.bits[k/32], ~(1 << (k%32))); }

int testbit (BitBlock_t a, uint32_t k) { return (a.bits[k/32] & (1 << (k%32))) != 0; }

void * sieveoferatosthenes (void * vid) { long tid = (long) vid; for (uint32_t j = getnext(); j <= val; j = getnext()) { for (uint32_t p = 2; p *p <= val; p++) {

if (testbit(b, p) != 1) { for (uint32_t i = p * p; i <= val; i += p) { setbit(b, i);

} } } }

pthread_exit(EXIT_SUCCESS);

}

int getnext(void) { static int next = 0; int cur = 2; pthread_mutex_lock(&b.mutex); cur = next++; pthread_mutex_unlock(&b.mutex); return cur; }

int main(int argc, char *argv[]) { int opt = -1;

pthread_t *threads = NULL; long tid = 0; /* for(int i = 0; i < block_num; i++) { pthread_mutex_init(&b[i].mutex, NULL); b[i].bits = 0; } */ while ((opt = getopt(argc, argv, "t:u")) != -1) { switch (opt) { case 't': num_threads = atoi(optarg); break; case 'u': val = atoi(optarg); break; default: /* '?' */ exit(EXIT_FAILURE); break; }

}

block_num = (val + 31) / 32; b.bits = (uint32_t *) calloc(block_num, sizeof(uint32_t)); pthread_mutex_init(&b.mutex, NULL);

threads = malloc(num_threads * sizeof(pthread_t)); if(isVerbose) { fprintf(stderr, "number of threads: %d", num_threads); fprintf(stderr, "upper bound: %d", val); }

for (tid = 0; tid < num_threads; tid++) { pthread_create(&threads[tid], NULL, sieveoferatosthenes, (void *) tid); }

for (tid = 0; tid < num_threads; tid++) { pthread_join(threads[tid], NULL); }

for (uint32_t p = 2; p <= val; p++) { if (testbit(b, p) != 1) printf("%u ", p); }

free(threads); pthread_mutex_destroy(&b.mutex); free(b.bits);

return EXIT_SUCCESS; }