#/***********************************************************
#    primroot.rb -- 原始根
#***********************************************************/
N = 168
$prime = []

def generate_primes
    $prime[0] = 2;  x = 1;  k = 1
    while (k < N) 
        x += 2;  j = 0
        while (j < k && (x % $prime[j]) != 0); j += 1; end
        if (j == k); $prime[k] = x; k += 1; end
    end
end

def modpower(n,  r,  m)  # pow(n, r) % m 
    t = 1
    while (r != 0) 
        if ((r & 1) == 1); t = ((n * t) % m); end
        n = ((n * n) % m);  r /= 2
    end
    return t
end

def primitive_root(k)
    i = 0;  p = $prime[k];  n = p - 1
    for i in 0...k
        a = $prime[i]
        j = 0; while (j < k)
            break if (n % $prime[j] == 0 &&\
                      modpower(a, n / $prime[j], p) == 1)
        j += 1
        end
        if (j == k); return a; end
    end
    return 0;  # error, primitive root not found 
end

generate_primes()
printf("素数と原始根\n")
printf("%5d( -)", $prime[0])
for i in 1...N
    if (i % 7 == 0); printf("\n"); end
    printf("%5d(%2d)", $prime[i], primitive_root(i))
end
printf("\n")

exit 0