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]
It's an integer factorisation program
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:
- Given an integer N, generate a lengh-N string.
- Match the string by the regex.
- Divide N by the length of the matched group.
- 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