素数と遊んでみた

#素数?
1 と 自分自身以外の数字で自分を割れなかったら、その子は素数です。
小数は、素数となりえないので、
例えば、2 , 3 , 5 , 7 , 11 ..  は素数です。

ちゃんとした説明はこちらです。
https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

#判定して遊んでみた
例えば n を素数か否かを判定しようと思います。
分かっている判定基準は以下です。

>1 と 自分自身以外の数字で自分を割れなかったら、その子は素数です。。

だったら、2 ~ n-1 で n を割ってみて、割り切れるか否かを確かめていきます。
具体的には、以下の通りです。

・n を 2 で割る。 => 割り切れた? Yes or No
・n を 3 で割る。 => 割り切れた? Yes or No
・n を 4 で割る。 => 割り切れた? Yes or No
・n を 5 で割る。 => 割り切れた? Yes or No
・n を 6 で割る。 => 割り切れた? Yes or No
・n を 7 で割る。 => 割り切れた? Yes or No
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
・n を n-1 で割る。 => 割り切れた? Yes or No

以上の工程の中で 1 度でも Yes が出たら、その子は素数ではありません。

```judge_prime_factor.py
def fun1(n):
    if n == 1:             # 1 を判定しようとしたら迷わず False を return
        return False      

    for i in range(2,n):   # for 文で n を割る数は 2 ~ n-1 に設定
        if n%i == 0:         # もし n が 2 ~ n-1 で割り切れたら
            return False     # False を return

    return True            # 前述の for 文で一度も False にならなければ
                           # n は素数です
```

但し、上記の記述だと判定すべき数字が大きい場合、
for 分を沢山回す必要があります。それはそれは効率が悪い事この上ない。
そこで落ち着いて状況を整理します。
例えば。。。

```check_divisor_of_n.py
  # n を約数に分解してみます。
  # 素数を含む場合もあれば、素数を含まない場合もあります。

  # 例1:↓左項に注目
   20 = 1 * 20   # 1 は置いておいて左項の 2 or 4 で 20 が 
      = 2 * 10   # 割れてしまえば、20 は素数ではない。
      = 4 *  5   # っと言えます。。

  # 例2:↓左項に注目
   30 = 1 * 30   # 1 は置いておいて左項の 2 or 3 or 5 で 30 が
      = 2 * 15   # 割れてしまえば、30 は素数ではない。
      = 3 * 10   # っと言えます。。
      = 5 *  6   
```

前述にある 20 , 30 の例に出てきている **1, 2 ,4** or **1, 2 , 3 , 5** は何者!?
察してる方も多いと思いますが、彼らは n の平方根より小さい人たちです。

```math
\sqrt{20} ≒ 4.47\\
\sqrt{30} ≒ 5.47
```

以上の理由から fujitanozomu さんの仰る通り、全部やる必要ないのです。

取り急ぎ参考例を用意しました。
記述では平方根を取った n の**小数点以下の切り捨て**に floor を使っています。
fujitanozomu さんのコメントあるように while 文での実現する場合は、
floor なんて不要です。

```judge_prime_factor.py
from math import *                        #floor を呼び出すための記述
def fun1(n):
    if n == 1:                            
        return False
                                          # floor は小数点以下を切り捨て
    x = floor(n ** (0.5))                 # n**(0.5):=> n を 1/2 乗
    for i in range(2,x+1):                # range は最終値は見ないので +1 を忘れずに
        if n%i == 0:
            return False

    return True
```

#素数に分解して遊んでみた。
前述の判定処理を流用して分解していきます。

例えば 
4 を素数に分解すると 2 x 2 
20を素数に分解すると 2 x 2 x 5  

アプローチとしては
n を一番小さい素数で割り切れなくなるまで割ります。
割り切れなくなったら、次に大きい素数で割り切れなくなるまで割ります。
以上のように一番小さい素数から n-1 までに含まれる素数で同じ作業を繰り返し行います。

・n を 2 で割り切なくなるまで割った? 割れる度に 2 をメモで保存
・n を 3 で割り切なくなるまで割った? 割れる度に 3 をメモで保存
・n を 5 で割り切なくなるまで割った? 割れる度に 5 をメモで保存
・n を 7 で割り切なくなるまで割った? 割れる度に 7 をメモで保存
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・
&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;・

【例】20 を分解してみる
&emsp;&emsp;i) 2 で割りまくる
&emsp;&emsp;&emsp;1回目:20/2 = 10
&emsp;&emsp;&emsp;2回目:10/2 = &ensp;5
&emsp;&emsp;&emsp;3回目:&ensp;5/2 =>割り切れん、次だ!!

&emsp;&emsp;ii) 3 で割れないので Pass!

&emsp;&emsp;ii) 5 で割りまくる
&emsp;&emsp;&emsp;1回目:5/5 = 1..終わり!

コードに落としてみますが、
POINT は素数が冒頭に 2, 3 と続いていることです。

```divid2prime_factor.py
def fun2(n):
    lis = []                   # 素数を保存するメモ
    
    for i in range(2,n):       # 割りまくる数字を 2 ~ n-1 とする
        while True:              # while を使い,割り切れなくなるまで繰り返す作業を実現
            if n%i == 0:         # n が i (=2,3..) で割り切れる? yes or no 
                lis.append(i)    # 割り切れたらメモ。
                n = n//i         # ex) 20/2 = 10 なので n を 20 から 10 に更新
            else:
                break            # 割り切れなくなったら while を break

    if not len(lis):           # 1個も素数が無かった場合、
        lis.append(n)          # n そのものが素数なのでリストにメモ
    return lis

#input example
print(fun2(20))
print(fun2(30))

#output example
[2, 2, 5] # answer of fun2(20)
[2, 3, 5] # answer of fun2(30)
```

###分解作業でも計算量を減らせるのか？
試してみましょう。
前述のコードにあるように素数で割れたらメモする考え方を流用します。
但し、n を割る値の範囲は 2 以上 floor(n の平方根)以下とします。

```check_divisor_of_n.py
  # 例1: n = 20, n を割る数字を 2以上 4 以下とする
   20 = 2 * 10       #← 2 で割る: 1 回目...list.append(2) : [2]
      = 2 *  2 * 5   #← 2 で割る: 2 回目...list.append(2) : [2,2]
  # for 文では range(2,5) まで為、処理はココで終了

  # 例2: n = 30, n を割る数字を 2以上 5 以下とする
   30 = 2 * 15       #← 2 で割る: 1 回目...list.append(2) : [2]
      = 2 *  3 * 5   #← 3 で割る: 1 回目...list.append(3) : [2,3]
      = 2 *  3 * 5   #← 5 で割る: 1 回目...list.append(5) : [2,3,5]
  # for 文では range(2,6) まで為、処理はココで終了 
```

例 1 の場合は、素数 5 を lis に回収できずに終わってしまいました。
しかし、例 2 の場合は、素数 5 まで回収することが出来ました。
この違いは何でしょうか？

**[答え]:**
規定した範囲の数値で割り切った後、 n == 1 の場合,素数の全回収が出来てると判断できる。
しかし、割り切っても n != 1 の場合、素数の全回収が出来ないので、
最後に残った n を素数としてリストする。

上記の**"答え"**を盛り込んだコードであれば計算量を削減して
素数へ分解できそうです。

```divid2prime_factor.py
from math import *
def fun2(n):
    lis = []                  
    x = floor(n**(0.5))          
    for i in range(2,x+1):       # range なので x は x+1 にする
        while True:              
            if n%i == 0:         
                lis.append(i)    
                n = n//i         
            else:
                break            
    if n > 1:                    # n が 1 より大きければ 例1 と同じ
        lis.append(n)
    return lis

#input example
print(fun2(20))
print(fun2(30))
print(fun2(2))
print(fun2(5))
print(fun2(19))
#output example
[2, 2, 5] # answer of fun2(20)
[2, 3, 5] # answer of fun2(30)
[2]       # answer of fun2(2)
[5]       # answer of fun2(5)
[19]      # answer of fun2(19)
```

#分解後の素数が何個含まれているか、要素ごとに数えてみた
前述にあるように"分解して遊んだ"あとに count を使えば良いのですが、
辞書の記述を使うアプローチもあると思いますので、書いてみました。

ちょっと、そこに行く前に、
辞書について補足するためのサンプルを用意しました。

```dictionaly_sample.py
def dic(n):                            # dic 詳細
    dic = {}                              # メモ用紙を準備
    for i in n:                           # 1 2 3 3 4 5 2 を一個ずつ i に代入
        if i not in dic:                    # dic に i にあるかどうか確認
            dic[i] = 0                         # dic に i がなければ dic[i] = 0 と初期化
        dic[i] += 1                            # dic[i] += 1
    return dic                              # dic の編集が終わったら return で返す!

n = list(map(int,input().split()))  # データを input
print(dic(n))                       # n を dic 関数に突っ込んだ結果を print 表示

# input example
# 1 2 3 3 4 5 2
# output
# {1: 1, 2: 2, 3: 2, 4: 1, 5: 1}
# => 1 が 1 個
# => 2 が 2 個
# => 3 が 2 個
# => 4 が 1 個
# => 5 が 1 個
```

今までの考え方と前述の辞書を組み合わせると
因数分解した素数が何個あるのかメモすることが出来ます。
前述の "divid2prime_factor.py" に辞書を追加します。

```Count_prime_factor.py
def fun3(n):
    dic = {}
    for i in range(2,n):
        while True:
            if n%i == 0:                
                if i not in dic:    # ココから=> 
                    dic[i] = 0      # 素数をカウントして記録(辞書) 
                dic[i] += 1         # ココまで<=
                n = n//i                
            else:
                break
    if not len(dic):
        dic[n] = 1
    return dic

print(fun3(20))
##output
#{2: 2, 5: 1}
# => 2 が 2 個
# => 5 が 1 個
```

###計算量を削減したバージョンも記載しておきます。
```Count_prime_factor.py
from math import *
def fun3(n):
    dic = {}
    x = floor(n**(0.5))
    for i in range(2,x+1):
        while True:
            if n%i == 0:
                if i not in dic:   
                    dic[i] = 0      
                dic[i] += 1         
                n = n//i
            else:
                break
    if n > 1:                  # n>1 の時は前述の for 文で判別できなかった素数
        dic[n] = 1             # それは 1 個だけのはずです。
    return dic
```