DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets Manager

Snippets has posted 5883 posts at DZone. View Full User Profile

Check For Primality With A Regexp

03.18.2007

| 9178 views |

        Original perl code here:

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

class Fixnum
  def prime?
    ('1' * self) !~ /^1?$|^(11+?)\1+$/
  end
end

Tags:

Comments

Snippets Manager replied on Wed, 2011/03/23 - 12:11pm

Not exponential, but proportional to the length of the Fixnum in unary. For sufficiently large numbers, this will quickly eat all your swap space. I tried it for fun, and indeed, Mac OS complained about running out of disk space. How badly this really behaves depends on the Ruby VM and your system's memory manager. Anyway, not good.