{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2023年度計算機演習A・B\n",
    "\n",
    "# 第8回：素数の判定"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 繰り返し文におけるbreak\n",
    "\n",
    "これまでの授業で学んできたように、Pythonでは処理の繰り返しを行うためにfor文とwhile文が用意されています。\n",
    "\n",
    "for文は決まった回数の繰り返し、while文はある条件が成り立つ間の繰り返しを行うものですが、通常の終了の前に繰り返しを強制的に終了する必要がある場合には`break`を使用します。\n",
    "\n",
    "次のコードのように、基本的には何かしらの条件判定を行うif文を入れてその中に`break`を書きます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result = 1\n",
    "\n",
    "for n in range(1,100):\n",
    "    result = result*n\n",
    "    if result >= 5000:\n",
    "        break  #for文を強制的に終了\n",
    "\n",
    "print(\"条件「nの階乗が5000以上」を満たす最小のnは\",n)\n",
    "print(\"その階乗の値は\",result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "なお、for文またはwhile文のネスト（入れ子）の場合は、`break`を実行する最も内側の繰り返しのみが強制的に終了されます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 剰余演算と因数の判定\n",
    "\n",
    "整数nをmで割り算をしたときの余りを計算するために、「剰余演算(mod)」を使用します。\n",
    "Pythonのプログラミングでは、`%`という剰余演算子を使用して余りの計算は可能です。\n",
    "\n",
    "例えば、23を5で割ると、商は4となり、余りは3となります。このあまり計算は以下のコードで算出できます。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=23\n",
    "m=5\n",
    "n%m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "あまり計算を利用して、整数mが整数nの因数であるかどうかを判別可能です。\n",
    "\n",
    "即ち、 `n%m == 0`がTrueであれば、mはnの因数となります。\n",
    "\n",
    "以下のコードは100以下のランダムな整数に対して、奇数と偶数の判別を行います。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "15 is an odd number (奇数).\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "n = random.randint(2,100)  #2以上100以下のランダムな整数を与える\n",
    "print(n)\n",
    "\n",
    "if n%2 ==0:\n",
    "    print(\"%d is an even number (偶数).\"%n) \n",
    "else:\n",
    "    print(\"%d is an odd number (奇数).\"%n) \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 素数の判定\n",
    "\n",
    "**素数（prime number）**は、正の約数が $1$ と自分自身のみであるような $2$ 以上の自然数のことです。$2$ 以上の自然数のうち素数でないものを、**合成数（composite number）**と呼びます。\n",
    "\n",
    "与えられた $2$ 以上の自然数が素数であるかどうかを判定する方法はいくつか知られていますが、最もシンプルな考え方に基づいた方法として**試し割り法（trial division）**があります。\n",
    "\n",
    "試し割り法においては、与えられた $2$ 以上の自然数 $n$ に対して、$n$ が $2$ から $n-1$ までの数で割り切れるかどうかを小さい順に調べます。いずれかの数で割り切れれば $n$ は合成数であり、どの数でも割り切れなければ $n$ は素数という結論になります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "n = random.randint(2,100)  #2以上100以下のランダムな整数を与える\n",
    "print(n)\n",
    "\n",
    "flag = True  #素数判定のためのフラグ（bool型の変数）　Trueは真\n",
    "\n",
    "for m in range(2,n):  #m=2からn-1まで繰り返す\n",
    "    if n%m == 0:  #nがmで割り切れるなら（%は余りを求める演算子）\n",
    "        print(m,\"で割り切れるので、合成数である\")\n",
    "        flag = False  #フラグをFalse（偽）にする\n",
    "        break  #for文を強制的に終了\n",
    "\n",
    "if flag:  #bool型の変数を使った条件判定\n",
    "    print(\"素数である\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "補足： 上記のコードに使用した変数`flag`の役割を確認してください。`flag`の最初の値はTrueであり、forループの計算では因数一つを見つかった場合、`flag`の値をFalseに変更して、ループを終了します。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 注意：\n",
    "\n",
    "$n$ が自分自身でない $\\sqrt{n}$ より大きな約数をもつ場合には、$n$ は $1$ でない $\\sqrt{n}$ より小さな約数も必ずもちます。\n",
    "\n",
    "したがって、割り切れるかどうかを調べるのは、実際には $n-1$ ではなく $\\sqrt{n}$ 以下の最大の自然数までで十分であることが分かります。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習1\n",
    "\n",
    "$2$ 以上の自然数 $n$ に対してそれが素数なら`True`、合成数なら`False`を返す関数`is_prime(n)`を定義して、`is_prime(43)`と`is_prime(91)`の値を表示してください。\n",
    "\n",
    "（オプション）可能であれば、上記の注意を反映したコードにすること。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習1のコード\n",
    "def is_prime(n):\n",
    "    #ここに、関数の処理を書く\n",
    "    #合成数ならreturn Falseとする\n",
    "    return True\n",
    "\n",
    "print(is_prime(43))\n",
    "print(is_prime(91))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習2\n",
    "\n",
    "演習1で定義した関数`is_prime(n)`を用いて、小さい順に $1$ 番目から $20$ 番目の素数を格納したリストを作成してその値を表示してください。\n",
    "\n",
    "さらに、作成したリストを用いて、素数の番号と値の関係を表すグラフを描画してください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習2のコード\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "prime_list = []\n",
    "\n",
    "#ここで、prime_listに要素を追加する\n",
    "#while文とif文を使うとよい\n",
    "\n",
    "print(prime_list)\n",
    "\n",
    "#ここで、グラフの描画を行う"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 演習3\n",
    "\n",
    "差が2である二つの素数の組を双子素数と呼びます。例えば、(17,19)は一つの双子素数の組です。\n",
    "\n",
    "is_prime(n)という関数を利用して、最初の100組の双子素数を算出してください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#演習3のコード\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第8回レポート課題\n",
    "\n",
    "演習1～演習3に取り組んでください。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}