20 ms·
Interesting, I wrote a quick script to use this: #!/usr/bin/env ruby def is_prime(n) ("1" \* n.to_i)!~ /^1?$|^(11+?)\1+$/ end num = ARGV.shift $stdout.p
by amp108 5y ago
Interesting, I wrote a quick script to use this:
#!/usr/bin/env ruby
def is_prime(n)
("1" \* n.to_i)!~ /^1?$|^(11+?)\1+$/
end
num = ARGV.shift
$stdout.puts is_prime(num)
... then decided to test it on a button-mashed number:
$ruby ~/prime.rb 767423
... and it hung.
Thought it was the length of the number, so I tried something smaller (101). Quick "true". Then I tried progressively more digits. I got to `ruby ~/prime.rb 7673121` (false) and it took less than a second.
But it doesn't like something about the number 767423.
- TrianguloY 5y agoThe regexp basically tests all dividers of the number (from 2 to the number-1), if it founds one, it says false and stops, if nothing is found, it says true. 101 is prime, but it does "only" a hundred checks approx. 7673121 is divisible by 3, so as soon as it tries to match groups of 3 it succeeds and stops. 767423 is prime, so it needs to do hundreds of millions of checks, that's probably why it hungs. Basically: the runtime of the algorithm should be equivalent to the minimum divisor excluding 1 of the number.