目次
エラトステネスの篩
ある正の整数N以下の素数を高速で求めるアルゴリズムです。計算量はO(NloglogN)となります。
python 3でのコード例。
N=int(input())
A=list(range(2,N+1))
p=list()
while A[0]**2<=N:
tmp=A[0]
p.append(tmp)
A=[e for e in A if e%tmp!=0]
print(p+A)
アルゴリズムはこちらのHPなどが詳しいです。
1行ごとにコードを説明します。
- 標準入力で正の整数Nを受け取ります。
- 2~Nまでの整数のリストを作ります。range関数で作ったイテレータをリストに変換して作りました。
- 素数を格納するリストを用意します。現時点では空っぽです。
- while文で以下の条件を満たす間、計算し続けます。すなわち整数リストの一番先頭が、Nの平方根以下である場合は計算し続けます。ただし平方根をつかいたくないのでリストの先頭の2乗がN以下である場合として処理します。
- 一時的な変数としてtmpにリストの先頭A[0]を代入します。
- 素数リスト「p」にtmp(つまりA[0])を追加します。
- 整数リストAのうち、リストの各整数をtmpで割ったあまりが0になるものは除外した新たなリストAを作ります。(処理的には、tmpで割った余りが0にならない(!=)もののみを残したリストAを作っている。)
リスト内包表記を使っています。 - while文を抜けたら、最終結果として、素数リストのpと残りの素数が入っている整数リストAを足して出力します。
素因数分解
計算量√Nの素因数分解のサンプルコードです。
N=int(input())
i=2
ans=dict()
n=N
while i*i <=N:
while n%i==0:
n=n//i
if i in ans:
ans[i]+=1
else:
ans[i]=1
i+=1
if n!=1:
ans[n]=1
print(list(ans.items()))
約数の個数を求める
約数の個数は、素因数分解の結果から求めることができます。各素因数の指数に1を加えて、全て掛け合わせれば約数の個数になります。
N=int(input())
i=2
ans=dict()
div_sum=1
n=N
while i*i <=N:
while n%i==0:
n=n//i
if i in ans:
ans[i]+=1
else:
ans[i]=1
i+=1
if n!=1:
ans[n]=1
ans_list=list(ans.items())
for j in ans_list:
div_sum*=j[1]+1
print(div_sum)
約数列挙
約数の全列挙。約数を求めたい数Nに対して、ルートNまでの範囲で、1から順にNを割り切ることができるか試していき、割り切れた時はその数と、その商をリストに記録していきます。最終的に得られたリストが約数のリストになります。
N=int(input())
ans=list()
i=1
while i*i<=N:
if N%i==0:
ans.append(i)
ans.append(N//i)
i+=1
ans.sort()
print(ans)