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); } }
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; }
素数計算で言語の練習
id:shawshank99に、素数を計算するプログラムを書いてみてよ、といわれ、素数ってなんだっけ?と聞き返すという駄目さ極まるところを見せてしまったので、題材は素数計算。ものすごく基礎的でガッカリですが、やらない事は忘れるので、基礎からナメまわすことにしました。それに、RSA暗号では素数使いますしね。問題としては、入力された数nまでの素数を出力するプログラムを書いてみます。
このコードでは、愚直にn回ループ内に2〜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に戻り値があるため可能な動作です。ブロックの中では、調べたい値を順に割り、その余りが0ならば、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の最後に&&がついててキモイという人もいるかもしれません。これは次のように1行であると見ると、多少分かり易いでしょう.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で実装してみることにします。
Macを開発用にセットアップする、その3。
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の違いというポストを見つけました。そういう意味だったのか。これは面白い。
しばらく設定が続いていますが、そろそろコードも書こうかな・・・。
Macを開発用にセットアップする、その2。
前回に続き、各種ツールのセットアップです。はじめに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のバージョン3だとわかりますが、一体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のインストールに続きますが、長くなりそうなので次回。
Macを開発用にセットアップする。
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など、ツール類のセットアップを行う事にします。次回へ続く。