素数

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

  • if文の説明は教科書40~45ページを参照する。
  • while文は教科書53~54ページを参照する。

1. Python言語の流れ制御

1.1 if文

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

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

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

if 文の書き方

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

説明

  • 「else」の部分を使用しなくでも良い。

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

In [24]:
def myabs(x):
    if x > 0:
        return x
    else:
        return -x
In [25]:
# myabsの処理を確認します。
print(myabs(3))
print(myabs(-3))
3
3

複雑なif文

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

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

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

In [28]:
x=15
if x % 2 == 0:
    print("因子2を持っています")
elif x % 3 == 0:
    print("因子3を持っています")
elif x % 5 == 0:
    print("因子5を持っています")
else:
    print("5以下の因子を持ってないです。")
因子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に超えるとき終了します。

In [16]:
sum = 0
i = 0
while sum < 100:
    i = i+1
    sum = sum+i
    print(sum)

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

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

ヒント:

  • max_valueという変数を用意して、xの各成分と比較します。ある成分がmax_valueより大きいであれば、max_valueの値をその成分の値に更新します。
  • max_valueの初期値をリストxの一番目の成分の値にします。
In [27]:
def my_max(x):
    pass
In [10]:
#テストためのコード。my_maxを完成したら、以下のコードを実行して、結果を確認しなさい。
x=[2,3,10,3,32,22,11]
my_max(x)

2. 素数の判別法

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

素数判別のアルゴリズム

  • 与えられるnについて、2からn-1までの整数mに対して、n % m ==0 の場合、mがnの因数となり、「素数ではない」という判定ができます。
  • 2からn-1までの数が因数にならないとき、「素数である」という判定ができます。

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

In [1]:
def is_prime(n):
    for m in range(2,n):
        if n % m == 0 :
            #print("因数 %d を持っています。"%m)
            return False        
    return True
In [22]:
is_prime(11)
Out[22]:
True

演習2

  • 2.1) 1000以下の2から最初の20個の素数を求めてください。
  • 2.2) 素数と素数の番号との関係図を描いてください。
In [21]:
#2.1)のコードのヒント

prime_list = []
num = 0
n = 2
while num < 20 and n < 1000:
    #コードをここに書いてください。
        
    n = n + 1
In [15]:
prime_list
Out[15]:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
In [29]:
#2.2)のコードのヒント

import matplotlib.pyplot as plt
plt.plot(prime_list,'.')
plt.grid()

演習3(オプション)

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

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

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