Pythonでプログラミング練習

プログラミング練習の定番？素数表示プログラムについて。普通にやれば

def prime1(n):
        #普通の素数表示プログラム
	for i in range(2,n):
	         for j in range(2,i+1):
			if i % j == 0:
				break
		if i == j:
			print i, ' ',

のようにするのだと思うけど、これは遅すぎる！実際にこれを実行してみると、自分のパソコンで100までの素数を表示するのにおよそ0.5秒、1000までの素数となるとおよそ5秒くらいかかってる。表示の仕方も人間の目で追える程度の速度で体感的にもずっと遅く感じて不満たらたら。

なのでもっと速いプログラムを書いてみた(元ネタはちょっと前に読んだ本だけど何だったか忘れた。それとPython用に自分でちょっと改造してある。

def prime(n):
        #処理回数の優秀な素数表示プログラム
	i,j = 5,1
	prime = [2,3]
	while i <= n:
		flag = 0
		while prime[j]**2 <= i:
			if i % prime[j] == 0:
				flag = 1
			j = j + 1
		j = 1
		if not flag:
			prime.append(i)
		i = i + 2
	print prime

このプログラムだとたとえ10000までの素数でも一瞬で出るし、100000でもおよそ3秒程度で出た。プログラム内部の処理回数は上のプログラムの1/10くらいだったと思う。もうこれで十分だけど、もっと速い素数表示プログラムはどんなのになるんだろう。こういう問題を追及した本とかサイトとかがあったらいいんだけど。

10000までの素数表示

※追記：もしかすると素数をリストで一度に表示しているから速く感じるのかもしれない。つまり1つ1つ順番に素数を表示することと、リストにまとめてそれを一度に表示することの差ということ。たぶんそんな気がする。いまの時代のコンピュータがそんなに遅いとは思えないし・・・。まあいずれにせよ処理回数の優秀な〜の方のプログラムは他のと比べて表示までの時間が速いのは確か。

余談だけど、個人的に繰り返し文はやっぱりCやJavaの方がPythonより使いやすい気がする。たとえば上のプログラムの

while prime[j]**2 <= i:
	if i % prime[j] == 0:
		flag = 1
	j = j + 1
j = 1

はCやJavaと同じようなfor文で書くことができれば

for(int j=1; prime[j]*prime[j]<=i; j++) {
     if(i % prime[j] == 0)  flag = 1;
}

で簡単に書くことができるのにPythonのfor文はなんとなく使いづらいというか、なかなか慣れない・・・(ちなみに上のPythonの方のプログラムで最後のj=1を入れ忘れて、どうしてうまくいかないのだろうと小1時間以上悩んでた。ほんとに（ ；∀；)ｲｲﾊﾅｼﾀﾞﾅｰ ）