找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 

输出：

​​

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^2-n的余数，那么需要Wilson定理的全部能力。对于这个问题，所有你需要知道的是它不是零。

在任何情况下，您都可以编写一个运行素数检查的程序，但是否这将被认为是有效的解决方案取决于分配问题的人。