2004-03-15
[Ruby]素数を求めよ
10000以下の素数を
2 3 5 7...
の形で標準出力に表示せよ。
ある人にC言語の宿題として出した問題だが、Rubyで書くとたとえばこうなる。所要時間10分。
def sosu?(n)
(2..n-1).each{|i|
return false if n%i == 0
}
true
end
def print_sosu(max)
(2..max).each{|n|
print n.to_s + ' ' if sosu?(n)
}
end
print_sosu(10000)
アセンブラをイメージしてみる。所要時間5分。
def sosu?(n)
i = 2
while(i < n)
a = n%i
if a == 0
return 0
end
i += 1
end
return 1
end
def print_sosu(max)
n = 2
while(n <= max)
a = sosu?(n)
if a != 0
print n
print ' '
end
n += 1
end
end
手動でZ80のアセンブラにしてみる。以下はsosu?メソッドのみである。おそらく255とか127でオーバーフローしてしまう。それ以外にもバグがあるかも知れない。所要時間90分。
GL_SOSU:
LD D,2 ;D = 2
LL_LOOP:
LD A,B ;while(D < B) => (B-D>0)
SUB A,D
JR Z,LL_LOOP_END
PUSH BC ;A = B%D
LD A,B
LD B,D
CALL GL_AMARI
POP BC
XOR A,0 ;if A == 0
JR NZ,LL_IF_END
LD A,0 ;rerutn 0
RET
LL_IF_END:
INC D ;D += 1
JR LL_LOOP ;
LL_LOOP_END:
LD A,1 ;rerutn 0
RET
GL_AMARI:
SUB A,B ;%
RET Z
JR NC,GL_AMARI
ADD A,B
RET
そしてマシン語。左側の二桁の数字の並びが機械語のプログラムである。すべてはここに行き着くわけで、まるで映画のマトリックスのように不思議だ。
0000 16 02 LD D, 02 0002 78 LD A, B 0003 92 SUB A, D 0004 28 11 JR Z, 0017 0006 C5 PUSH BC 0007 78 LD A, B 0008 42 LD B, D 0009 CD 1A 00 CALL 001A 000C C1 POP BC 000D EE 00 XOR A, 00 000F 20 03 JR NZ, 0014 0011 3E 00 LD A, 00 0013 C9 RET 0014 14 INC D 0015 18 EB JR 02 0017 3E 01 LD A, 01 0019 C9 RET 001A 90 SUB A, B 001B C8 RET Z 001C 30 FC JR NC, 001A 001E 80 ADD A, B 001F C9 RET
ちなみにCで書くと、
#include <stdio.h>
int is_sosu(int n)
{
int i = 2;
while(i < n) {
if(n%i == 0)
return 0;
i++;
}
return 1;
}
void print_sosu(int max)
{
int n = 2;
while(n <= max) {
if(is_sosu(n))
printf("%d ",n);
n++;
}
}
int main()
{
print_sosu(10000);
return 0;
}
whileはforにしたほうがよりCらしい。
int is_sosu(int n)
{
int i;
for(i=2 ; i<n ; i++) {
if(n%i == 0)
return 0;
}
return 1;
}
void print_sosu(int max)
{
int n;
for(n=2 ; n<=max ; n++) {
if(is_sosu(n))
printf("%d ",n);
}
}