Taylor Liesnham - 5 months ago 54
C Question

# How do I chunk prime numbers for multithreading?

I'm relatively new to C, and up until now had barely any experience in multithreading. I've written a small program that calculates whether an array of numbers are primes or composites. This works fine, but when working with larger numbers I'd like to split the workload between threads.

I sort of have an idea of how this would work, I just can't see how to implement this within C. As a simple example if we take the prime 199, I would divide this number by the number of cores (e.g. 4) to get 49.75. We would then round this number to 50. Each thread would then be given a range to calculate.

The first thread would calculate from i 2 to 50, the second from i 51 to 102, and so on.

I hope that makes some sense, I'm sure the solution is easier than I think it is, it's just I can't for the life of me work it out.

My Code:

``````#include <pthread.h>
#include <inttypes.h>
#include <stdio.h>
#include <unistd.h>

#ifdef _SC_NPROCESSORS_ONLN
#else
#endif

uint64_t numbers[] = {7,3,19,17,199,333}; // Numbers to check

void *work(void *n_void_ptr);
int isPrime(uint64_t n);

int main()
{
int rc;

for (int i = 0; i < sizeof(numbers) / sizeof(uint64_t); i++) {
}

return 0;
}

void *work(void *n_void_ptr)
{
uint64_t *n_ptr = (uint64_t *)n_void_ptr;

if (!isPrime(*n_ptr)) {
printf("%llu is a prime!\n", *n_ptr);
}

}

int isPrime(uint64_t n)
{
int count = 0;
uint64_t i; // Any number > n/2 cannot be a factor

for (i = 2; i < n / 2 - 0.5; i++) {
if (n % i == 0) {
count++;
}

if (count == 1) {
printf("%llu is composite!\n", n);

return -1; // n is not prime
}
}

return 0; // n is prime
}
``````

So what you want to do is have different threads to check for different non overlapping ranges.

We need a struct first to pass the ranges to the workers. So we start with -

``````typedef struct {
int lower;
int upper;
int number;
int result;
} worker_range;
``````

Now in the main I am assuming you need to check 199 and each thread needs to check 50 values.

We start like this

``````worker_threads **ranges = malloc(sizeof(worker_threads*) * (199 / 50 + 1));
``````

Now we need to spawn the threads

``````int i;
for ( i = 0; i < 199 / 50 + 1; i++){ //Fix this so that extra threads are not spawned.
ranges[i] = malloc(sizeof(worker_range));
ranges[i]->number = 199;
ranges[i]->lower = 2 + i * 50;
ranges[i]->upper = range->lower + 50; //We are probably okay with a bit of overflow
range[i]->result = 0;
}
``````

Now that all threads have started, we wait for them to finish.

``````int flag = 0;
for ( i = 0 ;i < 199 / 50 + 1; i++) {
if(ranges[i]->result == 1)
flag = 1;
free(ranges[i]);
}
if (flag==1){
printf("%d is composite\n",199);
}else{
printf("%d is prime\n",199);
}
free(ranges);
``````

Finally the worker function -

``````void* work(void * param) {
work_range *range = param;
int i;
for(i = range->lower, i < range->upper; i++){
if (range->number % i == 0){
(range->result) = 1;
break;
}
}
}
``````

I hope this helps.