N！ n^2で割り切っています

Question

私はNを見つけなければならないプログラムを書くために見つける必要がある練習を持っています！ N^2で割る。
1≦N≦10^9
階乗関数を作成し、それをNのパワーに分割する簡単な方法でこれを行いたいと思っていましたが、明らかに機能しません。 nは、prime次いでn!が均等n^2で割り切れない場合 だけアルゴリズムまたは擬似コードは、任意n > 4について

Answer 1

十分だろう。ここで

は私の議論を支援するための簡単な説明です：n!後

がnによって分割され、我々はnによって分割する必要が分子に(n-1)!が残されています。従って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 

出力：これは数n > 1があれば素数であることを述べているより簡単によりWilson's Theoremかかわらに関連している

​​

Answer 2

場合によってのみ

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

これはのみの場合

n! = -n (mod n^2) 

さらに、それが知られており、簡単に

（Wikipediaの記事を引用する）ことを証明する場合n>1が素数であることを言うのと代数的に等価です4の唯一の例外を除いて、3！ = 6≡2（mod 4）、nが ならば（n - 1）！ 0（mod n）と一致する。複合あるn場合従​​って4の唯一の例外と

、(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の残りの部分を残していることを示したい場合はウィルソンの定理の

フルパワーが必要とされています。この問題のために知る必要があるのは、ゼロではないということです。

いずれにせよ、素数チェックを実行するプログラムを書くことはできますが、それが有効な解決策とみなされるかどうかは、問題を割り当てた人が決まります。