Я знаю обычный способ итеративного поиска n-1 факториала с последующей проверкой. Но это имеет сложность O(n) и требует слишком много времени для больших n. Есть ли альтернатива?
Есть ли быстрый способ найти if (n-1)! делится на n?
Ответы (1)
Да, есть: если n — простое число, очевидно, (n-1)! не делится на n.
Если n не является простым числом и может быть записано как n = a * b с a != b, то (n-1)! делится на n, потому что оно содержит a и b.
Если n = 4, (n-1)! не делится на n, но если n = a * a с a простым числом > 2, (n-1)! делится на n, потому что мы находим a и 2a в (n-1)! (спасибо Юхане в комментариях).
person
alestanis
schedule
21.10.2012
чтобы найти, что n простое, не придется ли мне перебирать от 1 до n?
- person batman; 21.10.2012
Наивным методом было бы проверить числа от 1 до
sqrt(n) (а не n), чтобы увидеть, являются ли они делителями n, но это другой вопрос (stackoverflow.com/questions/2586596/).
- person alestanis; 21.10.2012
Как насчет идеальных квадратов? 4 не простое число, а
3! / 4 = 1.5.
- person JJJ; 21.10.2012
@Юхана ой! ты поймал меня! Отредактировал мой ответ.
- person alestanis; 21.10.2012
Это все еще не совсем правильно;
9 = 3 * 3 и 8! / 9 = 4480 (потому что 8! делится на 3*6, что равно 3*3*2).
- person JJJ; 21.10.2012
Хм... Будет ли 4 исключением? Все остальные совершенные квадраты дают (n-1)! делится на (n), то
- person alestanis; 21.10.2012
если
n=a*a, (n-1)! разделить на a^2 будет (a-1)!*(a+1)*(a+2)*...*(n-1) разделить на a. Итак, либо a делит (a-1)!, что является рекурсивным экземпляром исходной задачи, либо, если нет, нам нужно проверить, делит ли a верхнюю половину произведения (n-1)!/a! . В общем случае среди множимых будет 2*a, если a>2, потому что n=a*a. Например. для 8!/9 = (2)*(4*5*6*7*8) / 3 3*2 находится среди старших множителей произведения, поэтому 3 действительно делит его еще раз. Так что да, 4 является исключением. Это работает независимо от того, является ли a простым числом или нет: 4*4=16, 4*2=8, 16|(15!) === 4|(1*2*3)*(5*6*7*8*..*15) === true.
- person Will Ness; 22.10.2012
Да, n=4 (полный квадрат) является исключением: для всех n › 5 верно, что n является составным числом тогда и только тогда, когда (n=1)! mod n = 0, другими словами: (n-1)! делится на n тогда и только тогда, когда n не является простым числом. Различны ли факторы в n, не имеет значения. См., например, en.wikipedia.org/wiki/Factorial.
- person Bert te Velde; 25.10.2012
@alestanis: У тебя невероятно глубокий интеллектуальный ум.... :0 Великолепно и вдохновляюще :)
- person Jasmine; 26.02.2013
