"Числовые группы" C++

[badgo]

"Числовые группы".
Два натуральных числа, больших 1, назовем "связанными", если одно получается из другого умножением на какое-то простое число. Например, числа 2 и 10 связаны,а 21 и 85 нет. Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно подобрать цепочку чисел, их связывающую, такую, что каждые два соседних числа в этой цепочке связаны. Например, совокупность (3,6,30,51) - группа, а (3,4,6,30) нет. Напишите программу,которая по введенному натуральному числу n(2<=n<=10^9) выдавала бы количество групп, на которые распадается отрезок натурального ряда от 2 до n.

Помогите решить задачу.Несколько раз прочитал условие, ничего толком не понял. Что такое связанные числа разобрался, а про группу ничего не понял.

[caxap]

badgo в сообщении #369225 писал(а):

а про группу ничего не понял.

Возьмём любые два числа из {3,6,30,51}, напр. 6 и 51. Цепочка будет такая: (6,3,51) (соседние элементы связаны: $6=3\cdot 2$, $51=3\cdot 17$).

-- Вт ноя 02, 2010 15:11:00 --

Наверное я тоже что-то не понял, ибо второе множество тоже группа.
3 и 4: (3,6,2,4)
3 и 6: (3,6)
3 и 30: (3,6,30)
4 и 6: (4,2,6)
4 и 30: (4,2,6,30)
6 и 30: (6,30)
Может автор задачи подразумевал, что в цепочке разрешается использовать только числа из исходного множества? (Не люблю такие задачи, где авторы даже не потрудились ей качественно сформулировать.)

[badgo]

Вообщем бред какой-то)
Завтра еще уточню правильность условия.

[lim0n]

badgo в сообщении #369254 писал(а):

Вообщем бред какой-то

Всё сформулировано достаточно полно. Цепочки для группы ${3,6,30,51}$:
$3,6:\ (3,6)$
$3,30:\ (3,6,30)$
$3,51:\ (3,51)$
$6,30:\ (6,30)$
$6,51:\ (6,3,51)$
$30,51:\ (30,6,3,51)$

caxap в сообщении #369232 писал(а):

Наверное я тоже что-то не понял, ибо второе множество тоже группа.

При анализе Вы откуда-то берёте число $2$, а его во второй группе нет.
И вообще, видно, что все числа в группе должны иметь общий делитель, а во второй группе это условие не выполняется для пары чисел $3,4$.

[caxap]

lim0n в сообщении #369433 писал(а):

При анализе Вы откуда-то берёте число $2$, а его во второй группе нет.

Да, но ведь в задании не сказано, что можно брать числа только из рассматриваемого множества. Ну допустим, это подразумевалось.

lim0n в сообщении #369433 писал(а):

И вообще, видно, что все числа в группе должны иметь общий делитель

Множество {2,3,6} не имеет общего делителя (кроме 1), тем не менее
2,3: (2,6,3)
3,6: (3,6)
2,6: (2,6)

[lim0n]

badgo в сообщении #369225 писал(а):

Назовем совокупность натуральных чисел "группой", если для каждой пары чисел можно ...

Скорее всего имелось ввиду - "для каждой пары чисел группы можно ..."

lim0n в сообщении #369433 писал(а):

что все числа в группе должны иметь общий делитель

Да, с этим утверждением я погорячился.

[venco]

В общем, badgo, условия вроде уточнили.
А дальше надо подумать, какими должны быть два числа, чтобы между ними нельзя было проложить путь среди чисел <=n?

[badgo]

В общем ладно...Все равно ничего не понял...Забью на эту задачу пожалуй =)

(Оффтоп)

В общем или вообщем?

[venco]

(Оффтоп)

badgo в сообщении #369621 писал(а):

В общем или вообщем?

http://www.gramota.ru/slovari/dic/?word=%E2%EE%EE%E1%F9%E5%EC&all=x

[badgo]

(Оффтоп)

Угу,уже тоже погуглил)

[lim0n]

badgo в сообщении #369621 писал(а):

Забью на эту задачу пожалуй =)

Ну, а если серьёзно...

venco в сообщении #369528 писал(а):

какими должны быть два числа, чтобы между ними нельзя было проложить путь среди чисел <=n?

Если $p$ и $q$ - простые и $pq>n$, для них нельзя подобрать связывающую их цепочку. Как частный случай, при заданном $n$ в группе не может быть простых чисел $>\lfloor n/2\rfloor$. Но не вижу, что это может дать кроме максимального размера группы при заданном $n$.
А поиск групп? Построить группу максимального размера и после удалять из неё числа?.. Или наоборот, пойти снизу вверх (for i=2 to n)?.. Кстати, это мне больше нравится. Или искать пути в графе?.. Но уж больно условие "негуманное" ($2\le n\le 10^9$), таблица смежности получится немалая.

[venco]

lim0n в сообщении #370482 писал(а):

Если $p$ и $q$ - простые и $pq>n$, для них нельзя подобрать связывающую их цепочку.

Неправильно. $3$ и $5$ находятся в одной группе при $n=10$.

[lim0n]

venco в сообщении #370492 писал(а):

Неправильно.

Тут как раз - "Как частный случай ..." $2\cdot 5=10$

[venco]

lim0n в сообщении #370499 писал(а):

venco в сообщении #370492 писал(а):

Неправильно.

Тут как раз - "Как частный случай ..." $2\cdot 5=10$

Почему же "частный", если случай самый что ни на есть общий?

[lim0n]

Имелось ввиду, что при $n=10$, если в группе не будет числа $2$, то и число $5$ нельзя будет включить, т.к. нельзя найти связанное с ним число. В противном случае, действительно можно, например, определить такую группу $(2,3,5,6,10)$.