素数を数えるんだ

今日は休みだったのでn番目の素数を求めるプログラムを一日中書いていた。
カラフルな「果て無き方*1スーパーpre・シンタックスハイライト」を使うチャンスだ！

Perl

#Perlでn番目の素数を求める

print "何番目まで探す？ >";
$n_banme = <STDIN>;
chomp($n_banme);

#ゼロだったらとりあえず製作言語を表示
if( $n_banme <= 0 ){
	print "このプログラムはPerlで作られました。";
	exit(1); #異常終了ということにしておこう
}

#最初の素数2はあらかじめ素数配列に入れておく
$kazu = 2;
$sosuulist[0] = 2;
print "1:2\n";

if ($n_banme != 1){
	while(1){
		
		$kore_sosuu = 1; #foreachで約数が見つかったかどうかを示す
		$kazu++;
		
		foreach $sosuu (@sosuulist){
			if ($kazu % $sosuu == 0){
				$kore_sosuu = 0;
				last;
			}
			last if ($sosuu**2 >= $kazu); #2乗根以上の約数は調べなくていい
		}
		
		if ($kore_sosuu){
			$sosuulist[@sosuulist] = $kazu; #新しい素数を配列に追加
			print @sosuulist . ":" . $kazu . "\n";
			last if( @sosuulist == $n_banme );
		}
	}
}
print $n_banme . "番目の素数は" . $sosuulist[@sosuulist-1] . "です。";
exit (0);

見つけた素数を記憶しておいて素数判定に使ってみようという作戦。foreachを使ってみたいのでPerlで書いた。
素数が増えていくとメモリをどんどん使っていくからたくさん求めるのには向いていない。
lastをbreakと書いてしまった僕はまだPerlに慣れていないな。

Java

import java.io.*;

class sosuu{
	public static void main(String args[]) throws IOException{
		BufferedReader br =
			new BufferedReader(new InputStreamReader(System.in));
		System.out.print("何番目まで探す？ >");
		String nyuryoku_moji = br.readLine();
		int kokomade_sagasu = Integer.parseInt(nyuryoku_moji); //やっと入力が得られた・・・
		sagasu_sosuu(kokomade_sagasu);
	}
	//素数ならtrue、合成数ならfalse
	public static boolean sosuu_nano( int kazu){
		
		/* このプログラムでは6n+1と6n+5しか調べないからいらない部分
		//2,3,5は調べずとも素数とわかる
		switch(kazu){
			case 2:
			case 3:
			case 5:
				return true;
		}
		if ( kazu % 2 == 0 ) return false;
		if ( kazu % 3 == 0 ) return false;
		*/
		if ( kazu % 5 == 0 ) return false; //5の倍数はくるからこれは必要
		
		int yakusuu;
		//調べる数の2乗根以下の6n+1または6n+5で割ってあまりが出るか調べる
		for(yakusuu = 6; (yakusuu + 5)*(yakusuu + 5) <= kazu; yakusuu+=6){
			if ( kazu % (yakusuu + 1) == 0 ) return false; //6n+1
			if ( kazu % (yakusuu + 5) == 0 ) return false; //6n+5
		}
		if ( ((yakusuu + 1)*(yakusuu + 1) <= kazu) && (kazu % (yakusuu + 1) == 0) ) return false;
			//6n+1 < sqrt(kazu) < 6n+5 の場合の6n+1を調べる
		
		return true;
	}
	//n番目の素数を求める
	public static int sagasu_sosuu(int n_banme){
		
		if (n_banme <= 0){ //0番目の素数って何？それっておいしいの？
			//とりあえず製作情報を出してみる。
			System.out.print("このプログラムはJavaで作られました。"); 
			return 0;
		}
		
		//2,3,5が素数なのは知ってるので探すフリをする
		System.out.println("1:2");
		if (n_banme == 1) return 2; //1番目だけ知りたい場合もある
		System.out.println("2:3");
		if (n_banme == 2) return 3; //2番目まででいいときもある
		System.out.println("3:5");
		if (n_banme == 3) return 5;
		
		//6n+1,6n+5が素数かどうか調べる
		int sagasita = 3; //すでに素数は3つ見つけた
		int sosuu = 6; //この変数が6nの部分になる
		while(true){
			//6n+1
			if( sosuu_nano(sosuu + 1) ){
				System.out.println(++sagasita + ":" + (sosuu+1)); //これは消してもいいかもね
				if (sagasita == n_banme){
					sosuu += 1; //sosuuは6nになってるから直してからループ脱出
					break;
				}
			}
			//6n+5
			if( sosuu_nano(sosuu + 5) ){
				System.out.println(++sagasita + ":" + (sosuu+5));
				if (sagasita == n_banme){
					sosuu += 5;
					break;
				}
			}
			sosuu += 6;
		}
		System.out.println(n_banme + "番目の素数は" + sosuu + "です。");
		return sosuu;
	}

}

コメント多い。
6n+1と6n+5の形の数だけ調べる作戦。単純でない方法を使っていると利口になった気分がするので良い。
C用に書いたのをちょっと書き直しただけだったりする。

JavaScriptでも作ろうとしているが、インタフェースのhtmlに時間がかかりそう。それとは別に高速に動くのをCで書いてみようかな。

*1:はてな記法