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 has posted 5883 posts at DZone. View Full User Profile

Check For Primality With A Regexp

  • submit to reddit
        Original perl code here:

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


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

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.

Snippets Manager replied on Sun, 2007/03/18 - 12:59pm

That is really nifty. Slow as all hell I'd wager, though. Exponential time?