Return to Revisions

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円+$)

Try it online!

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 \0ドル \le c<d<k\$, thus \$a\$ will 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\$. For example, let one of the divisors be a prime power \$x=p^q>1\$ such that \$p^{q+1}\$ is not a divisor of \$n\$, and let the other one be \$y=n/x>1\$. Distribute \$x,y\$ into \$a,b\$ depending on which is larger. They will be coprime, so their least common multiple will be \$n\$. Thus, no number smaller than \$n\$, including \$a\$, will be divisible by both \$a\$ and \$b\$, and since \$a\$ is divisible by \$a\$, it will not be divisible by \$b\$.

# 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円+$)

Try it online!

Retina 0.8.2, (削除) 41 (削除ここまで) (削除) 39 (削除ここまで) 38 bytes

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

Try it online!