Pythonをいじってみた その１

ブログ記事再開の第1弾は、Pythonです。

いままで、C++やDelphi、C#といった言語を使ってきましたが、
Pythonが大きく異なる点は、型チェックが実行時にのみあるというところです。
まあ、スクリプト言語（インタープリター）なので当たり前ですが。

今回は、簡単なプログラムを作ってみたいと思います。

---

さて、プログラムのテーマなのですが、
リストなどを簡単に扱えるということで、素数を列挙するプログラムを書いてみたいと思います。

素数を見つけるアルゴリズムは、「エラトステネスのふるい」です。
とはいっても、当たり前の方法です。

目標：Nまでの素数を見つける

１．２からNまでの整数を全部書き出した表をつくる
２．表のうち、一番小さいものは素数（最初は２）
３．表から、その素数で割れるものは全部消す
４．表に数が残っていれば、2番に戻る

小さい順に素数をみつけていき、それで割れる数を消していくってことですね。

実に単純な方法ですが、それ以上に効率のいい方法というのもなさそうです。
（素数にいわゆる「規則性」みたいなものはないので）

最初に作ったプログラムリスト。
prime1.py

 1 #! c:/python27/python.exe
 2 
 3 
 4 def PrimeNumber():
 5     number_list = range(2,10000)
 6     number_list.reverse()
 7     prime_list = []
 8 
 9     while len(number_list)>0:
10         a = number_list.pop()
11         prime_list.append(a)
12         for x in reversed(number_list):
13             if x % a == 0:
14                 number_list.remove(x)
15     print "prime numbers are\n"
16     print prime_list
17 
18 
19 if __name__ == "__main__":
20     PrimeNumber()
21 

1行目は、スクリプト言語のお作法で、インタープリターのパスを指定しています。
4行目からがメインとなる関数の定義です。
まず、２から10000までの整数をいれたリストを作ります。
その後、リストを逆順にしているのは、リストは末尾から取り出すのが効率がいいので、
手順２を行うのに都合がいいのです。
そして、prime_listは素数のリストで、最初は空です。
while文以降は、数のリストが空っぽになるまで以下の処理を続けろ、という意味。
ここで、Pythonの特徴のひとつに、「ブロックはインデントで決まる」というのが使われます。
C言語系なら{}、Pascalならbegin-endなど、
たいていの言語では処理の構造を示す記号が決められています。
ところが、Pythonではインデントですべてが決められます。
これはコーディングの見た目が統一されるという意味で合理的かもしれません。

ループの中では、まず最初にリストの末尾から数字を取り出し、素数のリストに加えます。
次に、取り出した素数で割れる数字をリストから消します。
逆順に取り出しているのは、繰り返し処理の中でリストの要素を削除するという操作を行うとき、
その副作用がリストの繰り返し処理にどのような影響を与えるかわからなかったからです。

以上でアルゴリズムは終了ですが、
最後のところの処理でかなり処理コストがかかりそうです。
というのも、末尾から調べていくので、removeを実行した際に、
先頭から探して該当要素を消すとなると、その検索に時間がかかりそうだからです。

というわけで、次回はこの点を改良するとともに、
関数プログラミング的な要素を取り入れた変更を加えてみたいと思います。