Определить простоту числа

[kthxbye]

Определить простоту числа $q$, если разрешено делить нечетные числа из множества $\left\lbrace1,3,5,\cdots,q-6\right\rbrace$ на натуральные из множества $\left\lbrace1,2,3,4,\cdots,\frac{q-1}{2}\right\rbrace$.

[maxal]

Решето Эратосфена вообще не требует делений.

[kthxbye]

maxal в сообщении #1548983 писал(а):

Решето Эратосфена вообще не требует делений.

Как и перестановки A057032, A057033, A057063, согласен. А если число относительно большое? Конечно, есть малая теорема Ферма. Однако в данной теме обсуждается конкретная задача с конкретными ограничениями.

[eugensk]

Для 4 множества пустое и с одной единицей, какой вывод я должен сделать насчет простоты?

[kthxbye]

eugensk в сообщении #1548987 писал(а):

Для 4 множества пустое и с одной единицей, какой вывод я должен сделать насчет простоты?

Благодарю за комментарий! Во избежание подобных ошибок, необходимо было заранее оговорить, что как минимум $q$ нечетное и $q>8$.

[mihaild]

Не очень понятно, что можно делать? Например поделить $q - 6$ на $2$, потом умножить обратно, прибавить $6$ и проверить на простоту любым известным методом разрешено? Если нет, то что значит "разрешено делить"?

[kthxbye]

mihaild в сообщении #1548990 писал(а):

Не очень понятно, что можно делать? Например поделить $q - 6$ на $2$, потом умножить обратно, прибавить $6$ и проверить на простоту любым известным методом разрешено? Если нет, то что значит "разрешено делить"?

Делить, т.е. отнимать какое-то количество раз и находить остаток. Да, скорее всего "разрешено делить" необходимо заменить на "разрешено находить остаток от деления".

[worm2]

Ну вот стандартная процедура: делим $q$ на $p$, либо пока нацело не поделим, либо пока $p^2$ не превысит $q$.
Но тут по условию нельзя $q$ на $p$ делить.
Ну и что? Можно вместо этого $q-2p$ на $p$ делить с тем же результатом, кажется, это разрешено?

[kthxbye]

worm2 в сообщении #1548994 писал(а):

Можно вместо этого $q-2p$ на $p$ делить с тем же результатом, кажется, это разрешено?

Абсолютно точно, это и есть предполагаемое (и элементарное) решение.