F
Ftf 3k3
I tried to follow the instructions here:
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
It doesn't work as expected... any help would be very appreciated.
class Integer
def is_prime?(k)
if self % 2 == 0
return 'NO'
end
n = self
d = n - 1
s = 0
while d % 2 == 0
d /= 2
s += 1
end
k.times do
a = rand(n - 1) + 1
t = true
for r in 0...s
if (a ** d) % n == 1 or (a ** ((2 ** r) * d)) % n == -1
t = false
end
end
return 'NO' if t == true
end
return 'YES'
end
end
STDIN.gets.to_i.times do
puts STDIN.gets.to_i.is_prime?(25)
end
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
It doesn't work as expected... any help would be very appreciated.
class Integer
def is_prime?(k)
if self % 2 == 0
return 'NO'
end
n = self
d = n - 1
s = 0
while d % 2 == 0
d /= 2
s += 1
end
k.times do
a = rand(n - 1) + 1
t = true
for r in 0...s
if (a ** d) % n == 1 or (a ** ((2 ** r) * d)) % n == -1
t = false
end
end
return 'NO' if t == true
end
return 'YES'
end
end
STDIN.gets.to_i.times do
puts STDIN.gets.to_i.is_prime?(25)
end