$\sqrt{M}$まで試し割りすればよいので$O(\sqrt{M})$。

なんとなくfactorに投げてみたが、普通に書いた方が楽だったと思う。 何かの拍子にWAになって再提出になりそうだし。

#!/bin/bash
read line
a=1
b=1
for n in `factor $line | cut -d: -f 2` ; do
    if [ $a -eq 1 ] ; then
        a=$[$a * $n]
    else
        b=$[$b * $n]
    fi
done
echo $a $b