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

2025年5月8日出題

1. $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$ ずつ増やしていけば良い。