ある整数 $n$ の約数を全て探すとき，普通は $1$ から $n$ までを走査するfor文で1つ1つ約数判定を行う．この場合の計算量は $O(n)$ であり，制約が $n \leq 10^9$ のような競プロのコンテストでは通常通らないと考える．

しかし， $n=a \times b$ を満たすような整数ペア $a, b (a \leq b)$ を考えると， $a \leq\sqrt{n}$ を満たすため，これを利用することで $O(\sqrt{n})$ で約数を全列挙できる．

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	for a := 1; a*a <= n; a++ {
		if n%a != 0 {
			continue
		}

		b := n / a
		fmt.Println(a)
		fmt.Println(b)
	}
}

ちなみにこれは Atcoder ABC112 D で使用した．実はGoで書くと $n$ が $10^9$ でも通るのだけど，まぁ増やされたらそれまでなのでまとめてみた．

ついに同解法でGoなら通るがPythonだと駄目ってのを観測した pic.twitter.com/Qd6V2PsGgX

— raahii (@raahiiy) March 23, 2019