Помогите пожалуйста решить задачку
Задача: Даны 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 шт):
Проверка на то, что число вида 2^p*3^q (например - 12,27,72,64):
while (n%2==0)
n/=2;
while (n%3==0)
n/=3;
if (n==1) - ДА!
Задача в целом же не полностью определена - если достаточно найти любое подмножество - просто ищем пару чисел, одно из которых делится на другое.
Если же нужно найти максимальное подмножество - это выглядит как задача о максимальной клике на графе, и сложновато для текущего учебного уровня (например, можно использовать алгоритм Брона-Кербоша)