Pythonで実装するエラトステネスの篩:素数の高速列挙

エラトステネスの篩

ある正の整数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行ごとにコードを説明します。

  1. 標準入力で正の整数Nを受け取ります。
  2. 2~Nまでの整数のリストを作ります。range関数で作ったイテレータをリストに変換して作りました。
  3. 素数を格納するリストを用意します。現時点では空っぽです。
  4. while文で以下の条件を満たす間、計算し続けます。すなわち整数リストの一番先頭が、Nの平方根以下である場合は計算し続けます。ただし平方根をつかいたくないのでリストの先頭の2乗がN以下である場合として処理します。
  5. 一時的な変数としてtmpにリストの先頭A[0]を代入します。
  6. 素数リスト「p」にtmp(つまりA[0])を追加します。
  7. 整数リストAのうち、リストの各整数をtmpで割ったあまりが0になるものは除外した新たなリストAを作ります。(処理的には、tmpで割った余りが0にならない(!=)もののみを残したリストAを作っている。)
    リスト内包表記を使っています。
  8. 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)