Revision e6e404e3-32b2-4a11-b581-d788f15e3bef - Code Golf Stack Exchange

# Regex (ECMAScript), <s>35</s> <s>33</s> 32 bytes

*-2 bytes thanks to H.PWiz* 
*-1 bytes by returning to the original algorithm, by a different angle (slower, but not exponentially so)*

```
^(?!(((x+)x+)(?=2円+$)2円*3円)1円+$)
```

[Try it online!](https://tio.run/##Tc0xT8MwEAXgv9JGSL1riJsUxNDgdGLo0gFGApKVXJ0D145s05ZSfnsIAxLSG57eN7w3dVCh8dzHLPTckt87@06fg5eWjpNH0g@nHuAsq8V8eIX1FABOKY6BtayX6RXWy3l9g3Ux1mG@OKOI7il6thpQBMMNwd11dotYHjs2BGCkJ9UatgSIU2k/jMEvLY0IveEIs2yGJe8ArNTCkNWxw2p5uXDYqi2w7JUPtLER9HP@gvgH9B9sVayL1S9j7Lw7Jht7UIbbiVdW02qSpKbcOQ8l30sqOU1xPExOifDUk4rAKPYqNh14xMbZ4AwJ4/S4l99DkRV5nv8A "JavaScript (SpiderMonkey) – Try It Online")

The 35 byte version was [written in 2014](https://gist.github.com/Davidebyzero/9090628#gistcomment-1177373) by teukon and me.

This works by asserting that there do not exist any \$a\$ and \$b\,ドル both proper divisors of \$n\$ where \$a>b\,ドル for which \$a\$ is not divisible by \$b\$.

This will always be true when \$n\$ is of the form \$p^k\$ (a prime power), because we will have \$a=p^c\$ and \$b=p^d\$ where \$k > c > d \ge 0\,ドル thus \$a\$ will always be divisible by \$b\$.

But if \$n\$ is not of the form \$p^k\,ドル there will always be at least one counterexample \$a,b\$ such that \$a\$ is not divisible by \$b\$. Trivially we can choose two different prime factors of \$n\,ドル and they will not be mutually divisible.

```
# For the purpose of these comments, the input number will be referred to as N.
^(?! # Assert that the following cannot match
 ( # Capture 1円 to be the following:
 ((x+)x+) # Cycle through all values of 3円 and 2円 such that 2円 > 3円 > 1
 (?=2円+$) # such that 2円 is a proper divisor of N
 2円*3円 # Cycle through all values of 1円 > 2円 that aren't divisible
 # by 2,円 by letting 1円 = 2円 * A + 3円 where A >= 0
 )
 1円+$ # where 1円 is a proper divisor of N
)
```

---

Bonus: Here is a 28 (27🐌) byte regex that matches numbers of the form \$p^k\$ where \0ドル \le k \le 2\$: 
`^(?!((x+)x+)(?!1円*2円+$)1円+$)`, exponential slowdown 🐌 version: `^(?!((x+)+)(?!1円*2円+$)1円+$)` 
(`(x+)+)` is equivalent to `(x+)x*` but exponentially slower)

[Try it online!](https://tio.run/##TY1BT8JAEIX/CjQmzFC7tMZ4oC6cPHDhoEfRZFOG7eiw2@yugIi/vdaDicnLy8v3Hd6bOZjYBO5SETveUth7906ffdCOjqNHsg@nDuCsF7Np/wrLMcApxyHD3FTTzU1@hZtqqH46O6NK/ikFdhZQReGG4O66uEWsjy0LAYgOZLbCjgBxrN2HCH5ZLSp2wgkmxQRr3gE4bZWQs6nFxc3lwnFt1sC6MyHSyiWwz@UL4p@g/8ItqmU1/9WY2uCP2codjPB2FIyzNB9ludQ7H6Dme0015zkOh9kpU4E6MgkY1d6kpoWA2HgXvZASbwdef/dVUZVl@QM "JavaScript (SpiderMonkey) – Try It Online")

This was inspired by the algorithm used by [Bubbler's APL answer](https://codegolf.stackexchange.com/a/220062/17216). The full prime power version of that would be `^(?!((x+)(?=2円+$)x+)(?!1円*2円+$)1円+$)`, but that's 36 bytes.

And [user41805's APL answer](https://codegolf.stackexchange.com/a/220353/17216) ported to regex is: 
[`^(?!(xx+)1円*(?=1円*$)x(xx+)2円*$(?<=^2円+))`](https://tio.run/##TY5Bb8IwDIX/CquQalMatRwpoacduHDYjmOIqDUhU5Z0ToBKwG9nZdOkXZ6s99nP70OdVGjYdDF3vqU7yxfSz30Hr5GN04LVeXffQv0EfZ/hppxALQcdY/9rzCZjqBdyu5lliPedCNY0BOU0LxErpq@jYYKUSbXWOEpRNMMcaeUi8V4NqxfjumOcd@wbCkGE2Bp3Q@EdpD8XUyuXFy2tCJ01EdI8xcrsAZzUwpLT8YDL2fVqwlqtwchOcXikg34r3hH/AP0HblnW5fyBMR7Yn5OVOylr2hErp2k@SjJb7T1DZRaSKpNlODxM@kQwdUN5MCg@VWwOwIiNd8FbEtbrwa9ueC/zsiiKbw "JavaScript (Node.js) – Try It Online") - ECMAScript 2018, 40 bytes 
`^(?!(?*(xx+)1円*$)(xx+)2円*(?=2円*$)x1円*$)` - ECMAScript + `(?*)`, 39 bytes

# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), <s>41</s> <s>39</s> 38 bytes

```
.+
$*
^(?!(((1+)1+)(?=2円+$)2円*3円)1円+$)
```

[Try it online!](https://tio.run/##DYoxCsMwEMB2/aKQwDmGwN05bjyUjPmECc2QoUuH0v87Bg1C6Hf9P9@zjbK/2xwZJg7ZHiKiMXRke1WLQ6g2VQ9Vu7ZmOImVgmZswZ64kQq5V0XdlYz2LbMktPh6Aw "Retina 0.8.2 – Try It Online")