3 ms·
Simpler regexp: ^(11+)\1+$ it does not handle "1" for clarity. I also don't understand why author used `+?`, because simple `+` should work just as well.
by vbezhenar 5y ago
Simpler regexp:
^(11+)\1+$
it does not handle "1" for clarity. I also don't understand why author used `+?`, because simple `+` should work just as well. At least it works in Idea for me.
- MauranKilom 5y agoYeah, should work even with greedy matching as it just does the same checks but in reverse order.
- catlifeonmars 5y agoI wonder which one will reject composite numbers faster. The non greedy version starts with the smallest (potential) factor first, while the greedy version starts with the largest candidate factor first. I suspect that since a factor must be smaller than the square root of a composite, the greedy version you proposed would waste a lot of time checking numbers which could never be factors of the composite under test. If the number is prime, I think both variants have the same performance because they will exhaustively evaluate all numbers less than or equal to the composite under test. Edit: this is not quite correct. One of the prime factors must be smaller than the square root of the composite numbers, but the other one can obviously be larger. For example: 2 * 17 = 34. I’m leaving the original statement as is, because I’m hoping someone with a better math background can chime in and explain if the way that prime factors are distributed is symmetrical or not.