Sqrt-D&C

package main

import (
    "fmt"
)

func sqrt(x, l, r int) int {
    m := (l + r) / 2
    if (m+1)*(m+1) > x && m*m <= x {
        return m
    }
    if m*m < x {
        return sqrt(x, m, r)
    } else {
        return sqrt(x, l, m)
    }
}

func main() {
    // Example usage
    var n int
    fmt.Scan(&n)
    fmt.Println(sqrt(n, 1, n))
}