#/***********************************************************
#    lucas.rb -- 素数のLucasテスト
#***********************************************************/
N = 1000

def prime( p )
    a = []; x = []
    for i in 0...p; a[i] = 0; end
    a[2] = 1;  # a = 4 
    for k in 2...p
        for i in 0...p
            x[i] = a[i];  a[i] = 1
        end
        a[1] = 0;  # a = -2 mod M_p 
        for i in 0...p
            if (x[i] == 1) 
                s = 0;  h = i
                for j in 0...p
                    s = (s >> 1) + a[h] + x[j]
                    a[h] = s & 1;  h = (h + 1) % p
                end
                if (s > 1) 
                    while (a[h] == 1) 
                        a[h] = 0;  h = (h + 1) % p
                    end
                    a[h] = 1
                end
            end
        end
    end
    a[p] = 1 - a[0];  # 番人 
    i = 1
    while (a[i] == a[0]); i += 1; end
    return (i == p)
end

printf("2^p - 1 は素数かどうか調べます (p: 素数).\n")
printf("p? ");  p = gets.to_i
if (p < 3 || p > N); exit 1; end
if (prime(p)); printf("2^%d - 1 は素数です.\n", p)
else;          printf("2^%d - 1 は合成数です.\n", p)
end

exit 0