素数

本日の授業はプログラミングで素数を検討してます。また、Pythonのif文、whileループの文法を勉強します。

1. Python言語の流れ制御

1.1 if文

コードの流れを制御するために、if文, while文が使用されます。

「ある条件が満たされる場合、指定のコードを実行する」という条件分岐によってコードのながれの制御が考えられます。

例えば、与えられる数値xの絶対値を求めるとき、以下の条件分岐が利用されています。

if 文の書き方

if 条件式:
  条件式を満たす場合に実行する処理
else:
  条件式を満たさない場合に実行する処理

説明

以下はPythonのコードです。この処理を独自の関数myabsで書きます。

複雑なif文

多くの条件式があり、条件分岐が複雑な場合、elifを使用することができます。

以下のコードは与えられる整数の因子一つを探します。 条件式では、剰余算(割り算の余り)が使用されます。Pythonでは、「%」が剰余算の演算子です。

例えば、15 % 3 = 0, 14 % 3 = 2, 13 % 3 =1。よって、15は因子3を持っています。14と13は因子3をもってないです。

1.2 Python言語の条件式で使用される「比較演算子」と論理演算子

条件式がTrueまたはFalseを返す。

値の比較するために、較演習子が使用されます。例えば、「3>2」がTrue, 「3<2」がFalseとなります。

よく使用される「>」,「<」以外に、以下の比較演算子も利用できます。

演算子 意味 使用例
== 左辺と右辺が等しいときTrueを返す 20==20
!= 左辺と右辺が等しくないときTrueを返す 10!=20
>= 左辺が右辺以上のときにTrueを返す 30>=20, 20>=20
<= 左辺が右辺以下のときにTrueを返す 10<=20, 10>=10

条件式の論理演算子

2つの条件式の合成もできます。

論理演算子 使用方法 意味
AND演算(aかつb) (条件式a) and (条件式b) 2つの条件式両方がTrueであれば、結果がTrueとなります。 3>2 and 3>1
OR演算(aまたb) (条件式a) or (条件式b) 2つの条件式のいずれかがTrueであれば、結果がTrueとなります。 2<3 or 2>1

1.3 while文

Python言語では、forループ処理以外に、while文が使用されます。「指定される条件式が満たされる限り、ループ文を繰り返す」という処理です。

while文の書き方

while 条件式:
    処理コード

以下のコードは1からの整数を足して、足し算の和が初めて100に超えるとき終了します。

演習1:数列の最大値の計算

リストxの各成分から最大値を求める関数 my_max(x) を作ります。

ヒント:

2. 素数の判別法

自然数の中で、1より大きい、正の約数が1と自分自身のみであるものは素数です。この定義によって、ある自然数$n$が素数であるがとうかを判断するとき、$n$の約数(因数)があるがとうか確認すれば十分です。

素数判別のアルゴリズム

以下のコードでは与えられる$n$が素数であるがどうかを判別しています。

演習2

演習3(オプション)

演習2で使用する判別法は効率よくないことがあります。 例えば、$m$が$\sqrt{n}$以上になるとき,$m$が$n$の因数にならないです。よって、forループ処理では、$m$を$n-1$までにする必要がないです。 また、$m$を2から$\sqrt{n}$までの素数を使ってnの因数判定を行っても十分です。

上記のアイデアを利用して、is_prime()を改善して、効率を良くしてください。

計算機演習A・Bのノート「素数」 授業担当:劉雪峰  2020年6月1日