2024年度「プログラミング言語1」「プログラミング言語演習」のページ

1. 正整数 $n$ の素因数の個数を $f\left(n\right)$ とする。ただし、 $n$ を複数回割る素因数については、その回数分数える。すなわち、 $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$ と素因数分解できれば、 $f\left(n\right)=e_1+e_2+\cdots +e_k$ と定める。ただし、 $p_1$, $p_2$, …, $p_k$ は相異なる素数で、 $e_1$, $e_2$, …, $e_k$ は正整数とする。たとえば、 $360=2^3\times 3^2\times 5^1$ なので、 $f\left(360\right)=3+2+1=6$ である。

2. 正整数 $n$ の素因数の個数を $f\left(n\right)$ とする。ただし、 $n$ を複数回割る素因数についてについても1個と数える。すなわち、 $n={p_1}^{e_1}{p_2}^{e_2}\cdots {p_k}^{e_k}$ と素因数分解できれば、 $f\left(n\right)=k$ と定める。ただし、 $p_1$, $p_2$, …, $p_k$ は相異なる素数で、 $e_1$, $e_2$, …, $e_k$ は正整数とする。たとえば、 $360=2^3\times 3^2\times 5^1$ なので、 $f\left(360\right)=3$ である。

   正整数 $n$ を入力して、 $f\left(n\right)$ を出力するプログラムを書け。

$p$ と $q$ が素数で $p+1,p+2,\dots ,q-2,q-1$ がすべて合成数のとき、 $p+1,p+2,\dots ,q-2,q-1$ を素数砂漠という。この素数砂漠の長さは $q-p$ と定める。素数砂漠の長さは素数砂漠に属する合成数の個数よりも $1$大きいことに注意すること。

たとえば、 $14,15,16,$ は素数砂漠である。なぜなら、 $13$ と $17$ は素数であり、その間にある $14$ も $15$ も $16$ も合成数だからである。

素数砂漠の長さに上限はない。すなわち、どんな正整数 $n$ に対しても長さが $n$ 以上の素数砂漠が存在する。このことは簡単に証明できる。

1. $2$ 以上の整数 $x$ を入力し、 $x$ の値に応じて以下のとおり動作するプログラムを書け。

   • $x$ が合成数のとき、 $x$ が属する素数砂漠の長さを出力する。
   • $x$ が素数のとき、0を出力する。

ヒント

$n$ 以上の最小を素数を見つけるには、たとえば、 $i$ を $n$ から始めて、素数でない間 $i$ を $1$ ずつ増やしていけば良い。

$a$ と $d$ が互いに素な正整数ならば、初項が $a$ で公差が $d$ の無限等差数列 $a,a+d,a+2d,a+3d,a+4d,\dots$ は無限個の素数を含む。このことはディリクレの算術級数定理として知られている．ガウス(Johann Carl Friedrich Gauss, 1777–1855)が予想していたことを、1837年にディリクレ(Johann Peter Gustav Lejeune Dirichlet, 1805–1859)が証明した．

たとえば、 $2$ から始まり $3$ ずつ増える無限数列

には、無限個の素数

が含まれる。

1. 正整数 $a$, $d$, $n$ を入力し、初項が $a$ で公差が $d$ の無限等差数列に含まれる $n$ 番目の素数を出力するプログラムを書け。なお、 $a$ と $d$ は互いに素であると仮定してよく、そのことを確認するコードを含む必要はない。

   たとえば、 $a=2$, $d=3$, $n=5$ の時の値は $23$ である。

与えられた整数にできるだけ近い整数で二つの素数の積で表せるものを探す。

1. $4$ 以上の整数 $n$ を入力し、素数の積 $pq$ で $pq\le n$ をみたすもののうち、 $pq$ の値が最大となるものを求め、そのときの $pq$ の値を出力するプログラムを書け。

2. $4$ 以上の整数 $n$ を入力し、素数の積 $pq$ で $pq\ge n$ をみたすもののうち、 $pq$ の値が最小となるものを求め、そのときの $pq$ の値を出力するプログラムを書け。

実数 $x$ に対して、 $x$ 以下の素数の個数を $\pi \left(x\right)$ と書く。（円周率とは無関係）

大きな $x$ に対して、 $\pi \left(x\right)\approx x⁄\log x$ が成り立つことが知られている。この事実は素数定理と呼ばれている。（$\approx$ は「近似的に等しい」を意味する。世界的にはこちらのほうが流行っている）

1. 整数 $n$ を $3$ から $999999$ まで動かして、 $n$ と $\pi \left(n\right)$ と $n⁄\log n$ の表を出力するプログラムを書け。

2. 浮動小数点数 $x$ を入力して、 $\pi \left(x\right)$ と $x⁄\log x$ を出力するプログラムを書け。 $e<x<{10}^6$ と仮定してよい。 $x$ は整数とは限らないことに注意。