小テク集1:nの素因数は√n以下に1つはあるっていうお話。

$n (> 1)$ の正の約数を $a, b (a \leq b, n = a b)$ とおくと、
$n = a b \geq a^{2}$ すなわち $\sqrt{n} \geq a$

$a$ の素因数に $n$ の素因数あるよねって話。
逆に、 $\sqrt{n}$ 以下の素数で $n$ を割り切れなかったら $n$ は素数だと分かるわね。

素因数分解せよ

$(1) 193$
$(2) 391$

倍数判定法については前記事を参照せよ。

$(1) \sqrt{193} < \sqrt{196} = 14 (193 よりデカい最小の平方数で抑えると計算しやすい)$
$1 + 9 + 3 = 13 \dots \times 3, 19 - 3 \cdot 2 = 13 \dots \times 7$
$+ 1 - 9 + 3 = - 5 \dots \times 11, 193 = 195 - 2 \dots \times 13$

$∴ 193.$

$(2) \sqrt{391} < \sqrt{400} = 20$
$3 + 9 + 1 = 13 \dots \times 3, 39 - 1 \cdot 2 = 37 \dots \times 7$
$+ 3 - 9 + 1 = - 5 \dots \times 11, 391 = 390 + 1 \dots \times 13$
$- 3 \cdot 2 + 91 = 85 \dots ○ 17$