2007-12-17

Javaの場合の素数計算

Java

import java.io.*;

public class Prime
{
	static int FIRST_PRIME = 2;
	
	public static boolean is_prime(int i){
		for(int n=FIRST_PRIME; n<i-1; n++){
			if(i%n == 0){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br =
			new BufferedReader(new InputStreamReader(System.in));
			
		String str = br.readLine();
		int n = Integer.parseInt(str);
		
		for(int i=0; i<n; i++){
			if(is_prime(i) && i >= FIRST_PRIME){
				System.out.println(i);				
			}
		}
		
		System.exit(0);	
	}
}

2007-12-17

Cの場合の素数計算

#include "stdio.h"
enum{
	TRUE = 1,
	FALSE = 0,
	FIRST_PRIME = 2
};

int	is_prime(int i){
	int n;
	for(n=FIRST_PRIME; n<i-1; n++){
		if(i%n == 0){
			return FALSE;
		}
	}
	return TRUE;
}

int main (int argc, char const *argv[])
{
	int n,i;
	scanf("%i",&n);
	for(i=0; i<n; i++){
		if(is_prime(i) == TRUE && i >= FIRST_PRIME){
			printf("%i\n", i);
		}
	}
	return 0;
}

2007-12-17

素数計算で言語の練習

Ruby

id:shawshank99に、素数を計算するプログラムを書いてみてよ、といわれ、素数ってなんだっけ？と聞き返すという駄目さ極まるところを見せてしまったので、題材は素数計算。ものすごく基礎的でガッカリですが、やらない事は忘れるので、基礎からナメまわすことにしました。それに、RSA暗号では素数使いますしね。問題としては、入力された数nまでの素数を出力するプログラムを書いてみます。

このコードでは、愚直にn回ループ内に２〜n回ループですから、計算量はO(n^2)です。

FIRST_PRIME = 2
gets.to_i.times do |i|
    if (FIRST_PRIME...i).each{|n|
      if i%n == 0
        break(false)
      end
    } && i >= FIRST_PRIME
     puts i
  end
end

変な書き方のif式ですね。なんとeachを条件式に使っています。これは、eachに戻り値があるため可能な動作です。ブロックの中では、調べたい値を順に割り、その余りが０ならば、breakしています。ここでbreakに引数falseを渡す事で、breakしたときのeachの戻り値がfalseになります。さらにRubyではfalseとnil以外はすべて真という解釈をするので、すべて割り切れなかったとき、すなわち素数のとき、真が帰る仕組みになっています。
しかし、これではちょっと気持ち悪い書き方です。次のようにメソッドに分離した方がいいでしょう。

FIRST_PRIME = 2
def is_prime(i)
  (FIRST_PRIME...i).each do |n|
      break(false) if i%n == 0 
  end && i >= FIRST_PRIME
end
gets.to_i.times do |i|
  if is_prime(i) 
     puts i
  end
end

is_primeメソッドの中身、each~endの最後に&&がついててキモイという人もいるかもしれません。これは次のように１行であると見ると、多少分かり易いでしょう.rubyではメソッドの最後に書いた式がそのメソッドの戻り値になるため、これでtrue or falseが返ります。

def is_prime(i)
  (FIRST_PRIME...i).each {|n| break(false) if i%n == 0 } && i >= FIRST_PRIME
end

1-linerだとこうなります。

gets.to_i.times {|i|   if ((2...i).each{|n| break(false) if i%n == 0} && i>= 2) then puts i end}

ついでなので、Fixnumクラスにis_prime?メソッドを追加してみます。そうすると、数.is_prime?と呼ぶだけでtrueかfalseか分かって便利。

class Fixnum
  FIRST_PRIME = 2
  def is_prime?
    (FIRST_PRIME...self).each {|n| break(false) if self%n == 0 } && self >= FIRST_PRIME
  end
end

gets.to_i.times do |i|
     puts i if i.is_prime?
end 

puts 3.is_prime?  # これはtrue
puts 50.is_prime? # これはfalse

しかし、このままでは遅すぎて使い物になりません。6桁以上のnを入力するとすべて計算するのにひどく待たされます。素数の計算で有名なアルゴリズムに、エラトステネスの篩というものがあるので、実装してみましょう。

#受け取った数列の先頭を素数列に追加し、その倍数にあたる数を削除して返す。
def push_and_delete(nums, primes)
  num = nums.shift
  return nums.delete_if{|x| x%num == 0}, primes << num
end

nums, primes = push_and_delete((2..gets.to_i).to_a,[])

while(nums.max > (primes.max**2))
    nums, primes = push_and_delete(nums, primes)
end

puts (primes + nums).join(",")

愚直バージョンに比べて劇的に早くなりました。
勉強のために、愚直バージョンをCやJavaで実装してみることにします。

2007-12-16

Macを開発用にセットアップする、その3。

MacOSX subversion 設定

subversionをインストールしましょう。一人で開発する場合はバックアップ用途ぐらいにしか使わないかもしれませんが、チーム開発する際には欠かせないツールの一つでしょう。subversionには（それに限らずともですが）様々な導入方法があります。ともすると古いバージョンのものを導入してしまうので注意が必要です。実際のところ、macportsを使ってしまえば、あまり問題はありません。
いつものコマンド

$sudo port install subversion

おしまいです。しかし、macportsで導入したsubversionは環境によっては日本語メッセージが化けることがあります。svnと打って「使用方法を知りたいときは 'svn help' と打ってください。」とちゃんと表示されれば問題は無いのですが、そうでない場合は環境変数を設定します。

export LANG=ja_JP.UTF-8

このコマンドを,シェル起動時に読み込むファイル（.bashrcとか.profileとか）に追記しておきましょう。ついでに

export EDITOR=emacs

などと指定しておくと、commit時のメッセージを指定したエディタで編集できます。ここでTortoiseSVNのようにGUIを使いたいと思うなら、SCPluginというものがあります。参考URLは下記の通りです。
http://www.ohnaka.jp/wiki/wiki.cgi?page=Subversion
SubversionをSCPluginでsshでつないで使う on IntelMac
MacOSX版TortoiseSVN、SCPluginが復活してる件
今の時点ではversion0.7のインストーラがあるようなので、そっちを利用します。
http://scplugin.tigris.org/servlets/ProjectDocumentList?folderID=0&expandFolder=0&folderID=8892
すでにsubversionが導入されていれば、インストール後にリブートしてコンテキストメニュー（右クリック）を開くと項目が現れるはずです。認証時にauthorization failedが出る場合は、.svn/configを編集してstore-auth-credの設定をyesにする必要があります。また、どうしても失敗する場合はsvnコマンドを直接叩いた方が確実です。
蛇足ですが、authenticateとauthorizeの違いというポストを見つけました。そういう意味だったのか。これは面白い。

しばらく設定が続いていますが、そろそろコードも書こうかな・・・。

2007-12-15

Macを開発用にセットアップする、その２。

MacOSX 設定

前回に続き、各種ツールのセットアップです。はじめにmacportsをインストールします。macportsはFedoraでいうyum,Ubuntuでいうapt-getに相当するものです。詳しくはBeginning_OSXに書かれているので、ここでは記しません。ダウンロードツールとしてはwgetが好きなのでインストールします。macportsが正しくインストールされていれば、

$sudo port install wget

とするだけです。次にターミナルの設定ですが、Beginning_OSXではこのように書かれています。

シェル上で Unicode 文字列を正しく扱うためには、 leadline 5.0 に対応した bash 3.0 以上が必要となる。

bash3はBourne-Again Shellのバージョン３だとわかりますが、一体leadlineって何でしょう。調べてもそれらしきものは引っかかりません。まさかと思い、leadlineをreadlineに直して検索し直したところ、ちゃんと引っかかりました.スペルミスだったようです。
参考になるのは以下の二つのページ。
http://www.rinneza.com/junya/tech/solaris9_x86/os/readline_5.0.html
http://macwiki.sourceforge.jp/wiki/index.php/gnuplot#.283.2F4.29_readline-5.0_.E3.81.AE.E3.82.A4.E3.83.B3.E3.82.B9.E3.83.88.E3.83.BC.E3.83.AB
どうやら、readlineはコマンドライン編集用のライブラリのようです。知らなかった。Tigerのreadlineは2001年以降更新されていないようなので、前のバージョンをリネームしてから新しいバージョンを入れる必要があるようです。詳細は以下のページで書かれていますが、
http://www.cbrc.jp/~tominaga/tips/osx_gnuplot.html

$cd /usr/lib
$ sudo mv libreadline.dylib libreadline.dylib_original

前にあったライブラリを違う名前で退避してから新しいreadlineのconfigure&makeを行うと良いようです。

$tar xvzf readline-5.2.tar.gz
$cd readline-5.2
$./configure --disable-shared 
$make
$sudo make install

ここで、configureに --disable-sharedオプションがついている事に注意してください。これは共有ライブラリをビルドしないように指定するオプションです。これが無いとどうなるのでしょう。怖くて試せません。readlineは旧版が既にインストールされているため、共有ライブラリは不必要という事でしょうか？
次に進みます。bashは、もう予想がついているかもしれませんが、

$sudo port install bash

とするだけ。あとはBeginning_OSXの通りに設定を実行すれば問題はありません。この設定は.bashrcや.bash_profileを作らなくてはならないので若干面倒くさいのですが、全部掲載されているので別段難しい事でもありません。非常にすばらしいサイトです。
同じくemacs,nkf,lha,fontconfig,kinput2-macim,ghostscript(ヒラギノフォント使用)も

$sudo port install emacs
$sudo port install nkf
$sudo port install lha
$sudo port install fontconfig
$sudo port install kinput2-macim
$sudo port install ghostscript-fonts-hiragino

だけです。macportsもすばらしいユーティリティです。但し、各種の設定ファイルを忘れないようにしましょう。
さて、ページャとしては、有名なlessがデフォルトで使えますが日本語の使えるページャ（lv）が紹介されていたのでこれを使います。しかも、lessライクな検索用コマンドを追加したhackを用意してくださっているようなので、これをもらう事にします。本当にすばらs（略）

$sudo port install lv +lesslikeslash

では、動作確認をしてみましょう。このブログの記事を表示してみます。

$lv blog2_sjis

どうやら大丈夫そうですね。さて、このままではlsコマンドを使うと、日本語が化けます。オプションに-wコマンドをつける事で解決しますが、毎回-wとするのはめんどくさい話です。lsの設定で解決しましょう。そのほかにもgimp,Inkscapeなど必要に応じてmacportsでガンガンインストールできます。さて、いよいよsubversionのインストールに続きますが、長くなりそうなので次回。

2007-12-14

Macを開発用にセットアップする。

MacOSX 設定

MacOSX(Tiger,Intel)の開発用環境を整えようとし、手順含め解決法をメモとして残すものです。また、ここに書いてあるほとんどの手順は下記サイトによりわかり易く書かれているので、参照してみてください。
http://www.miko.org/~tatyana/tech/OSX/Beginning_OSX.html

OSX インストール後、最新版へアップデート。どうやらデフォルトではrootが無効になっているようです。X11を使うつもりなので各種アップデートが終わったら、rootを有効化しておきます。手順については以下のサイトで詳しく書かれているので、ここでは簡単に記しておきます。
http://docs.info.apple.com/jarticle.html?artnum=106290

アプリケーション＞ユーティリティ＞Netinfoマネージャを開き、メニューの「セキュリティ」から認証をえらんで、ユーザのパスワードを入力します。ここで認証するとおなじ「セキュリティ」メニューからルートを有効にすることが可能になります。

つぎに開発用ツールをインストール。便利なXcodeです。
Tiger用の最新版、xcode 2.5 がリリースされているようです。Xcodeは以下のサイトから入手できますが、ADCのオンライン会員（無料）になる必要があるようです。めんどくさい。
http://developer.apple.com/tools/download/

X11 もインストールします。X11はTiger付属のインストールディスクからインストールできます。ディスクを起動すると、ぱっと見X11のパッケージが見つからないので迷うかもしれません。僕は迷いました。おちついて、下の方へスクロールするとそこにインストール用のOptional Installsファイルを見つける事ができます。
これを起動してX11だけにチェックを入れてインストールします。

これでベースは完了。次はやっと、subversion,cyberduck,mi,textmate,firefox,wget,quicksilver,mysql,terminal,macportsなど、ツール類のセットアップを行う事にします。次回へ続く。

2007-12-14

MacOSX setup for development.(1)

toriaji2007-12-14