Styjun

I know the title is not the best description but it was the best I could do .
Long story sort, I am trying to get a range of numbers,
lets say for the example :


MIN: 0 and MAX: 10 ,
so the range would be 10 .


I want to divide the range in n fields (The user gives this this input, so it is variable) and then create n threads-children , using fork() , where each one will get its own sub-range of these numbers and execute some code using these numbers , actually its going to check if this number is a prime number or not.

So my problem is that I can't think of a formula to write so that the numbers will be equally split.

I tried:

 for(int i = 0; i<n; i++)
 //fork()
 int temp = MIN + (i*(RANGE/n));
 for(int a =; a< temp +(RANGE/n)+1; a++)
 //check if prime
 //other actions
 
 

But I know this will not work correctly because if we have 3 threads(n),it is going to check the ranges (0,3) , (3,6) , (6,9) because the

(RANGE/n) gives 3

That means that the last number , in this example the 10, will never be checked in cases where the division of the RANGE from the N number of children leave a remain.

Is there any smart way to split the range and check all the numbers by different number of processes each time ?
thanks in advance

How to get equal number of elements after range division leaving a remainder

Various approaches.

A key issues is if the 0 and 10 are both included in the integer range: Is it [0... 10] or [0... 10) or ...? Notice the ] or )? Let us assume the lists end-points are included and [0... 10] is 11 different integer values.

Note: There are extremes such as having 11 numbers divided into 12 groups.

The below forms the sub-range from the first 1/n part of the range, then the 1/(n-1) part of the remaining range, etc.

void range(int n, int inclusive_min, int inclusive_max) 
 printf("Range [%d %d] / %dn", inclusive_min, inclusive_max, n);
 for(int i = n; i > 0 && inclusive_min <= inclusive_max; i--) 
 int range = 1 + inclusive_max - inclusive_min;
 int sub_range = range/i;
 if (sub_range == 0) sub_range = 1;
 printf("Sub range [%d %d]n", inclusive_min, inclusive_min + sub_range - 1);
 inclusive_min += sub_range;
 


int main(void) 
 range(3, 0, 10);
 range(2, 0, 10);
 range(5, 0, 10);
 range(3, 0, 1);
 return 0;

Output

Range [0 10] / 3
Sub range [0 2]
Sub range [3 6]
Sub range [7 10]
Range [0 10] / 2
Sub range [0 4]
Sub range [5 10]
Range [0 10] / 5
Sub range [0 1]
Sub range [2 3]
Sub range [4 5]
Sub range [6 7]
Sub range [8 10]
Range [0 1] / 3
Sub range [0 0]
Sub range [1 1]

A more elegant solution, akin to Bresenham's line algorithm

void range(int n, int inclusive_min, int inclusive_max) 
 printf("Range [%d %d] / %dn", inclusive_min, inclusive_max, n);
 int range = 1 + inclusive_max - inclusive_min;
 int sub_range = range / n;
 int sub_range_res = range % n;
 int p = 0;
 for (int i = 0; i < n; i++) 
 int next = inclusive_min + sub_range;
 p += sub_range_res;
 if (2 * p >= n) // like p >= n/2 without integer truncation.
 p -= n;
 next++;
 
 if (next > inclusive_min) 
 printf("Sub range %d:[%d %d]n", i, inclusive_min, next - 1);
 
 inclusive_min = next;
 

Output

Range [0 10] / 3
Sub range 0:[0 3]
Sub range 1:[4 6]
Sub range 2:[7 10]
Range [0 10] / 2
Sub range 0:[0 5]
Sub range 1:[6 10]
Range [0 10] / 5
Sub range 0:[0 1]
Sub range 1:[2 3]
Sub range 2:[4 6]
Sub range 3:[7 8]
Sub range 4:[9 10]
Range [0 1] / 3
Sub range 0:[0 0]
Sub range 2:[1 1]

If your task is to verify if a number is prime, it is convenient that the larger numbers are in smaller groups (since it is more difficult to verify that they are prime numbers).

You could use a policy, started by MAX. Then create the following interval: MAX-1, MAX-2 for example (and so on) until you have the number of required ranges.