def exp(n, k, mod = nil)
	x = 1	
	r = n
	while k > 0
		x *= r if k & 1 == 1
		r *= r		
		if mod
			x %= mod
			r %= mod
		end
		k >>= 1
	end
	x
end

def gcd(m, n)
	if m < n 
		gcd(n, m)
	elsif n == 0
		m
	else
		gcd(n, m % n)
	end 
end

def fermat_test(n)
    a = 2 + rand(n - 2)
    return false if gcd(a, n) > 1
    return exp(a, n - 1, n) == 1
end

def prime?(n, k = 100)
    return (1..k).all? { fermat_test(n) }
end

