Помогите пожалуйста решить задачку

Задача: Даны N положительных целых чисел, которые не делятся ни на какие простые числа, кроме 2 и 3. Удалить из массива числа так, чтобы из любых двух оставшихся одно число делилось на другое.

Понимаю, что задача стоит в том, чтобы удалить числа, а не найти их но, стало интерестно как же реализовать цикл, который бы сам искал эти числа.

Вроде понимаю, что тут не должен быть не особо сложный цикл, но как-то все никак не могу его реализовать: то числа "левые" вылезают, то вообще ерунда получается, удалить из массива эти числа труда не составит, но вот найти их - это уже другой вопрос ...

И да, насчет массивов, я знаю что можно было использовать динамический массив, просто в универе требуют использовать пока этот метод, до тех пор, пока мы до них(динамических массивов) не дойдем.

Вот так пробовал реализовать(хотел найти сначала все простые числа от 4 до текущего числа, потом сделать проверку чтобы из всех простых чисел данное число делилось только на 2 и 3):

    ...

    srand((unsigned)time(0));
    const int maxLength = 100;

    int array[maxLength] = { 0 };
    int a_length = 101;

    while (a_length > maxLength)
    {
        std::cout << "Enter the length of array (less than 100): ";
        std::cin >> a_length;
    }

    int number = 0;
    int simple_numbers[maxLength];
    int simple_length = 0;
    int marker_simple = 0;
    int marker_number = 0;
    for (int i = 0; i < a_length; i++)
  a:{
        number = rand() % 101;
        if (number % 2 == 0 && number % 3 == 0 && number != 0)
        {
            for (int j = 4; j < number; j++)    // find all simple numbers from j to number
            {
                int k;
                for (k = 2; k < j; k++)
                    if (j % k == 0)
                    {
                        j++;
                        k = 2;
                        marker_simple = 0;
                    }
                    else
                    {
                        marker_simple++;
                    }
                if (marker_simple != j - k)
                {
                    simple_length++;
                    simple_numbers[simple_length - 1] = j;
                }
            }
            int z;
            for (z = 0; z < simple_length; z++)     //check: if number devide to anyone simple number besides the 2 and 3 than change the number
            {
                if (number % simple_numbers[z] == 0)
                {
                    goto a;
                }
                else
                {
                    marker_number++;
                }
            }
            if (marker_number != simple_length - z)
                array[i] = number;
        }
        else
        {
            i--;
            continue;
        }
    }

    ...

Ответы (1 шт):

Автор решения: MBo

Проверка на то, что число вида 2^p*3^q (например - 12,27,72,64):

while (n%2==0)
   n/=2;
while (n%3==0)
   n/=3;
if (n==1) - ДА!

Задача в целом же не полностью определена - если достаточно найти любое подмножество - просто ищем пару чисел, одно из которых делится на другое.

Если же нужно найти максимальное подмножество - это выглядит как задача о максимальной клике на графе, и сложновато для текущего учебного уровня (например, можно использовать алгоритм Брона-Кербоша)

→ Ссылка