素数を求める

たまたまとあるところで見つけた素数出力のJavaプログラム。

public class prime {
        public static void main(String[] args) {
                int p[] = new int[200];
                int cnt = 0;
                p[cnt++] = 2;
                System.out.println(p[0]);
                for(int i = 3; i <= 1000; i += 2){
                        boolean flg = true;
                        for(int j = 0; p[j] * p[j] <= i; j++){
                                if(i % p[j] == 0){
                                        flg = false;
                                        break;
                                }
                        }
                        if(flg){
                                System.out.println(i);
                                p[cnt++] = i;
                        }
                }
        }
}

これが「完璧」と書かれていて、少しもやっとした。

少し甘いところ

いや、ぱっと思いつく甘いところがあるんですよ。
割切れるか確認するj。0から始めてるでしょ。1で良いんです。
p[0]は2。iは必ず奇数なので、2では割切れないから。

あとさ、pの上限が200固定なのが嫌。
ま、いいんだけどさ。

とりあえず上記コードをなるべく忠実にUWSCスクリプトにしてみる。

DIM p[200]
cnt = 1
p[0] = 2
PRINT p[0]
FOR i = 3 TO 1000 STEP 2
        flg = TRUE
        j = 0
        WHILE p[j] * p[j] <= i
                IF i MOD p[j] = 0 THEN
                        flg = FALSE
                        BREAK
                ENDIF
                j = j + 1
        WEND
        IF flg THEN
                PRINT i
                p[cnt] = i
                cnt = cnt + 1
        ENDIF
NEXT

UWSCのFORは終了条件を式にはできないので、WHILEで代用した。

UWSC流に修正してみる

HASHTBL p
cnt = 1
p[0] = 2
PRINT p[0]
flg = 1
FOR i = 3 TO 1000 STEP 2
        FOR j = 1 TO LENGTH(p) - 1
                flg = i MOD p[j]
                IF p[j] * p[j] > i OR !flg THEN BREAK
        NEXT
        IF !flg THEN CONTINUE
        PRINT i
        p[cnt] = i
        cnt = cnt + 1
NEXT

可変配列といえば、HASHTBL。
1000まで固定なら168個しかないけどさっ！
割切れるかの判定ループを短くした。
FOR文の方が早いのでWHILEから書き換えた。
元の方が代入が少ないけど、行数が短くなる方をとってみた。

さて、ここからさらに計算量を少なくする方法や、行数を減らす方法はあるかしらん。