Найти, если N! деление на n^2

Question

У меня есть упражнение, которое требует найти программу, в которой вы должны найти, если N! делится на N^2.
1 ≤ N ≤ 10^9
Я хотел это с помощью простого способа создания факториальной функции и деления его на мощность N, но, очевидно, это не сработает. Просто алгоритм или псевдо-код будет достаточно

Answer 1

Для любого n > 4, если n является prime, то n! не равномерно делится на n^2.

Вот простое объяснение, чтобы поддержать мой аргумент:

После n! делится на n, мы остались с (n-1)! в числителе, который должен быть разделен на n. Поэтому нам нужно n или несколько из n в числителе для того, чтобы (n-1)! был равномерно делимым на n, чего не может быть, когда n является простым.

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

Надеюсь, что это поможет !!!

Редактировать: Вот простой код Python для вышесказанного. Сложность O(sqrt(N)):

def checkPrime(n): 
    i = 2 
    while i<n**(1/2.0): 
    if n%i == 0: 
     return "Yes" # non-prime, so it's divisible 
    i = i + 1 
    return "No" # prime, so not divisible 

def main(): 
    n = int(raw_input()) 
    if n==1: 
    print "Yes" 
    elif n==4: 
    print "No" 
    else: 
    print checkPrime(n) 

main() 

Вход:

7 

Выход:

No 

Answer 2

Это связано, хотя легче, чем Wilson's Theorem, который говорит о том, что число n > 1 является простым, если и только если

(n-1)! = -1 (mod n) 

Это алгебраически эквивалентно тому, что n>1 первична тогда и только тогда, когда

n! = -n (mod n^2) 

Кроме того, известно и легко доказать, что (цитата в статье Википедии)

За исключением 4, где 3! = 6 ≡ 2 (mod 4), если n равно композит, тогда (n - 1)! совпадает с 0 (mod n).

Следовательно, с единственным исключением 4, если n составное, (n-1)! = 0 (mod n) следовательно n! = 0 (mod n^2) и если n простое, n! = -n = n^2-n (mod n^2) поэтому n! не конгруэнтны 0 в этом случае.

Полная мощность теоремы Вильсона необходимо, если вы хотите, чтобы показать, что для простых n, n! оставляет остаток точно n^2-n при делении на n^2. Для этой проблемы все, что вам нужно знать, это то, что она не равна нулю.

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