Help with a logical programming task

[DenisAndreevich]

Hi. I need your help with a small logic problem. The essence of the task:

There are numbers from 1 to N, N = 50, you need to divide the numbers into several groups
so if one number is divided by another, then these numbers fall into different groups.
The result of this partition is M groups, for N = 50, M = 6.

Example:

N = 50
The groups turned out like this:
Group 1: 1
Group 2: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Group 3: 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49
Group 4: 8 12 18 20 27 28 30 42 44 45 50
Group 5: 16 24 36 40
Group 6: 32 48
M = 6

===========
N = 10
The groups turned out like this:
Group 1: 1
Group 2: 2 7 9
Group 3: 3 4 10
Group 4: 5 6 8

I was able to solve this problem using an array of arrays, where I wrote intermediate data and did a bunch of different array operations. Unfortunately, my algorithm when working with, for example, a billion numbers required up to 8 GB of RAM and could count up to 14 hours on a single processor. Adding the rest of the cores to the work of course reduced this time, but the problem of RAM consumption has not gone away.

I was able to make a faster algorithm, but I can't bring it to mind. Maybe someone here can help me?

int magicNumber = 50;
int groups = (int)(Math.Log(magicNumber, 2) + 1);


using (StreamWriter streamWriter = new StreamWriter("output.result"))
{
for (int i = 1; i < groups; i++)
{
if (i == 1)
{
streamWriter.Write("1");
}
for (int j = i + 1; j < magicNumber; j++)
{
if (j % i == 0)
{

}
else
{
streamWriter.Write(j + " ");
}
}
streamWriter.WriteLine();
}
Write("\n");

}

Result is:

1
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49
5 6 7 9 10 11 13 14 15 17 18 19 21 22 23 25 26 27 29 30 31 33 34 35 37 38 39 41 42 43 45 46 47 49
6 7 8 9 11 12 13 14 16 17 18 19 21 22 23 24 26 27 28 29 31 32 33 34 36 37 38 39 41 42 43 44 46 47 48 49


Expected result in the example.

Thank you in advance.

Continue reading...