問６：二分法

方程式 $f(x) = 0$ の解を求める方法として代表的なものに、二分法とニュートン法がある。二分法は、関数 $y=f(x)$が区間 $[a,b]$ で連続で、解が1つ存在するときに使える。

二分法による解法は、以下の通りである。

区間 $[a,b]$ を2つに分け、その中点をcとする。
$f(a)\cdot f(c)$ が負であれば、区間 $[a,c]$ の中に $x$ 軸との交点があるはず。
$f(a)\cdot f(c)$ が正であれば、区間 $[c,b]$の中に $x$ 軸との交点があるはず。

というのを繰り返す。

方程式 $e^x - 3 x = 0$ を、区間 [0, 1] に対する二分法を用いて解きなさい。ただし、誤差 $\epsilon < 0.00001$ とする。また、numpy, scipy, sympy などを使うと便利だが、この問題は二分法の理解とPythonでの実装の練習を兼ねているため、これらのライブラリを用いないこと。

# アウトプット例
0.61906128673

誤差 $\epsilon$ の値を変化させた場合にこのアルゴリズムの挙動がどう変化するか答えよ。
同様に方程式 $tanh X + X + 2 = 0$ の解を二分法で求めよ

問７：ニュートン法

方程式 $f(x) = 0$ の解を求める方法として代表的なものに、二分法とニュートン法がある。ニュートン法は、関数 $y=f(x)$ が単調連続で変曲点がなく、かつ $f(x)$ の導関数が求められるときに使える。

ニュートン法による解法は、次の通りである。

ある $x$ における接線を求め、その $x$ 軸との交点を求める。
その $x$ 軸との交点の $x$ 座標を新たなxとし、その $x$ における接線を求める。

というのを繰り返す。

方程式 $e^x - 3 x = 0$ を、ニュートン法を用いて解きなさい。ただし、計算は x = 0 からスタートし、$\epsilon < 0.00001$ としたとき以下の収束条件（のいずれか）を用いるものとする。

$|\ f(X_n)\ | < \epsilon$
$|\ X_{n+1} - X_{n}\ | < \epsilon$
$|\ (X_{n+1} - X_{n})\ /\ X_{n}\ | < \epsilon$
$|\ f(X_{n+1}) - f(X_{n})\ | < \epsilon$

また、numpy, scipy, sympy などを使うと便利だが、この問題は二分法の理解とPythonでの実装の練習を兼ねているため、これらのライブラリを用いないこと。

# アウトプット例
0.61906128673

上記の収束条件を変更したときにアルゴリズムの挙動がどう変化するか答えよ。
同様に方程式 $x^2 - 2 x + 1 = 0$ の解をニュートン法で求めよ。
同様に方程式 $e^x sin x - 2 x = 0$　$(0 < x < π)$ の解をニュートン法で求めよ。

問８：約数

整数 $n$ を入力すると、その約数を列挙する関数を作りなさい。また、そのアルゴリズムを説明せよ。

ただし、$1 \leqq n\leqq 10^6$ とする。

例8-1

n = 60

[2, 3, 4, 5, 6, 10, 12, 15, 20, 30]

例8-2

n = 136

[2, 4, 8, 17, 34, 68]

例8-3

n = 8075

[5, 17, 19, 25, 85, 95, 323, 425, 475, 1615]

問９：素数判定

整数 $n$ を入力すると、それが素数なら True、素数でなければ False を返す関数を作りなさい。また、そのアルゴリズムを説明せよ。

ただし、$1 \leqq n \leqq 10^6$ とする。

例9-1

n = 53

True

例9-2

n = 12357

False

例9-3

n = 941471

True

問10：素因数分解

整数 $n$ を入力すると、素因数分解する関数を作りなさい。また、そのアルゴリズムを説明せよ。