В общем, как все уже поняли, факториал тут не особо поможет. Это мне напомнило почему-то теорему Вильсона. Она даёт необходимое и достаточное условие того, что число простое. Но алгоритмически её трудно использовать.
Но где же \Omega(n)? Мы же просто ходим по массиву. Если уж быть совсем формальным, то приведённое в посте решение использует O(\log n) доп. памяти, да (на наши два-три указателя). Псевдокод лениво писать, но могу на вопросы ответить, если что-то всё же недосказанным осталось.
Ладно, не буду я занудствовать про то, всё или не всё сводится. =)
Но сведение этой задачи к сату есть, например, у Кнута. Весь код состоит из пары методов из четырёх строчек. Строка длины 177 нашлась (солвером Кнута же!) за несколько секунд. Невыполнимость формулы для 178 доказалась на моём самом обычном ноуте за пару минут.
Но сведение этой задачи к сату есть, например, у Кнута. Весь код состоит из пары методов из четырёх строчек. Строка длины 177 нашлась (солвером Кнута же!) за несколько секунд. Невыполнимость формулы для 178 доказалась на моём самом обычном ноуте за пару минут.
bash-3.2$ ./sat-waerden 5 5 178 | ./sat13 (178 variables, 7744 clauses, 38720 literals successfully read) ~ UNSAT Altogether 96953+18950937986 mems, 341878 bytes, 1000830 nodes, 921919 clauses learned (ave 18.6->11.9), 678634 memcells. (374087 learned clauses were trivial.) (352116 learned clauses were discarded.) (1506 clauses were subsumed on-the-fly.)