素数

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

1. Python言語の流れ制御

1.1 if文

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

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

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

if文の書き方

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

ただし、「else」の部分は使用しなくても良いです。

以下はPythonのコードです。絶対値を求める処理を独自の関数myabsとして書きます。

複雑なif文

多くの条件式があり条件分岐が複雑な場合には、elif(else ifという意味)を使用することができます。

以下のコードでは、与えられる整数の因数を1つ探します。 条件式では、剰余算(割り算の余り)が使用されます。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が素数であるかどうかを判定するとき、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のノート「素数」 授業担当:劉雪峰  2021年5月31日