Regex (ECMAScript), (削除) 35 (削除ここまで) (削除) 33 (削除ここまで) 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円+$)
The 35 byte version was written in 2014 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
(
((x+)x+) # Choose a value of 2円 > 1, and a value of 3円 < 2円
(?=2円+$) # such that 2円 is a proper divisor of N
2円*3円 # and then choose a value of 1円 that is not divisible by
# 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)
This was inspired by the algorithm used by Bubbler's APL answer. The full prime power version of that would be ^(?!((x+)(?=2円+$)x+)(?!1円*2円+$)1円+$), but that's 36 bytes.
Retina 0.8.2, (削除) 41 (削除ここまで) (削除) 39 (削除ここまで) 38 bytes
.+
$*
^(?!(((1+)1+)(?=2円+$)2円*3円)1円+$)
- 12.9k
- 2
- 71
- 55