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

[venco]

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

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

Ну так и рассмотрите группу с $2$. Что в неё можно включить?

[lim0n]

Все числа кроме $7$.

[venco]

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

Все числа кроме $7$.

Ну а теперь сформулируйте это для произвольного $n$.

[lim0n]

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

Ну а теперь сформулируйте это для произвольного $n$.

Если Вы о группе максимального размера, то об этом я уже писал выше - в неё входят все числа от $2$ до $n$ кроме простых $p>\lfloor n/2\rfloor$.

Но я то немного о другом... Если понимать условие задачи дословно

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

Напишите программу,которая по введенному натуральному числу $n$, $2\le n\le 10^9$, выдавала бы количество групп, на которые распадается отрезок натурального ряда от $2$ до $n$.

решение кажется слишком простым: для $n=2$ ни одной, т.к. группа должна быть "совокупностью натуральных чисел"; для $n=3$ тоже ни одной, т.к. числа $2$ и $3$ несвязанные; для $n>3$ единственная группа. И где тут программирование?
Я же рассуждал о максимальном количестве групп, которые можно построить из натурального ряда от $2$ до $n$.
Кстати, как вариант усложнения задачи - найти максимальное количество групп, на которые распадается отрезок натурального ряда от $2$ до $n$.

[venco]

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

[Day]

А мне вдруг показалось все очень простым.
Наверное, ищется все-таки минимальное количество групп, т.к. максимальное = n-1 (каждое число образует группу).
Все числа до n/2 и все составные <= n образуют одну большую группу. (от любого до любого можно добраться через умножение и деление на простое, не вылезая за n)
А вот простые >n/2 остаются в одиночестве, т.е. каждое из них образует одноэлементную группу.
Остается только подсчитать кол-во простых от n/2 до n
и прибавить 1.
Или я в чем-то ошибаюсь ?

[lim0n]

Day в сообщении #375368 писал(а):

А мне вдруг показалось все очень простым.
Наверное, ищется все-таки минимальное количество групп, т.к. максимальное = n-1 (каждое число образует группу).

Даже ещё проще.
Например, из условия

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

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

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

[Day]

linOn, Если пар чисел нет (множество пар - пусто) то об этих несуществующих парах можно говорить все, что угодно, и все будет правда!
Взгляньте сюда
topic36983.html