#素数?
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
・
・
・
・
・
・n を n-1 で割る。 => 割り切れた? Yes or No
以上の工程の中で 1 度でも Yes が出たら、その子は素数ではありません。
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 分を沢山回す必要があります。それはそれは効率が悪い事この上ない。
そこで落ち着いて状況を整理します。
例えば。。。
# 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 の平方根より小さい人たちです。
\sqrt{20} ≒ 4.47\\
\sqrt{30} ≒ 5.47
以上の理由から fujitanozomu さんの仰る通り、全部やる必要ないのです。
取り急ぎ参考例を用意しました。
記述では平方根を取った n の小数点以下の切り捨てに floor を使っています。
fujitanozomu さんのコメントあるように while 文での実現する場合は、
floor なんて不要です。
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 をメモで保存
・
・
・
【例】20 を分解してみる
i) 2 で割りまくる
1回目:20/2 = 10
2回目:10/2 = 5
3回目: 5/2 =>割り切れん、次だ!!
ii) 3 で割れないので Pass!
ii) 5 で割りまくる
1回目:5/5 = 1..終わり!
コードに落としてみますが、
POINT は素数が冒頭に 2, 3 と続いていることです。
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 の平方根)以下とします。
# 例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 を素数としてリストする。
上記の**"答え"**を盛り込んだコードであれば計算量を削減して
素数へ分解できそうです。
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 を使えば良いのですが、
辞書の記述を使うアプローチもあると思いますので、書いてみました。
ちょっと、そこに行く前に、
辞書について補足するためのサンプルを用意しました。
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" に辞書を追加します。
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 個
###計算量を削減したバージョンも記載しておきます。
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