Use regular expression to solve integer factorisation problem

0-main.rb

n = ARGV.first.to_i
fact = Hash.new(0)
while match_data = /^(.{2,}?)\1+$/.match('.'*n)
  fact[match_data[1].length] += 1
  n /= match_data[1].length
end
fact[n] += 1
puts fact.sort.map!{|k,v| "#{k}#{"**#{v}" if v > 1}"}.join(' * ')

1-README.md

Remarks

Run it with an integer as argument:

ruby entry.rb [INTEGER]

I confirmed the following implementations/platforms:

• ruby 2.2.3p173 (2015-08-18 revision 51636) [x86_64-darwin14]
• ruby 2.1.6p336 (2015-04-13 revision 50298) [x86_64-darwin14.0]
• ruby 2.0.0p645 (2015-04-13 revision 50299) [x86_64-darwin14.3.0]
• ruby 1.9.3p551 (2014-11-13 revision 48407) [x86_64-darwin14.1.0]

Description

It's an integer factorisation program

Internals

This program makes use of regular expression and its backtracking function to solve integer factorisation problem, the regex below will match strings whose length is a composite number.

/^(.{2,}?)\1+$/

All factors of the given number N can be found by the following steps:

1. Given an integer N, generate a lengh-N string.
2. Match the string by the regex.
3. Divide N by the length of the matched group.
4. Repeat step 2 and 3 until N become a prime number (not matched)

For example, let N = 18, we got a string like:

..................

First, .{2,}? will only match the first 2 characters .. since the question mark uses a lazy quantifier to minimize matching. Then \1+ tries to match the first group .. (I separate each group with spaces for clarity).

.. .. .. .. .. .. .. .. ..

It matches, and N will be divided by 2 (length of ..). In the next iteration, N = 9 and the string will become:

.........

Again, .{2,}? matches .., and \1+ tries to match the tailing string:

.. .. .. .. .

However, in this time it does not match since the tailing . is not equal to the group ... It makes .{2,}? backtrack and the group will become ...:

... ... ...

Now it matches again, and N will be divided by 3 (length of ...). In the next iteration, N = 3 and the string will become:

...

The regex can not match ..., so N remains 3. We can finally find all factors:

18 = 2 * 3 * 3
2: first divisor
3: second divisor
3: remained N