9. 整数アルゴリズム¶

簡単な整数問題からアルゴリズムとデータ構造の関係をみていきます。

9.1. モジュロ(mod)¶

剰余演算（モジュロ）は、整数 a を整数 b で除算し、余りをえる\(a \mod b\)です。

a % b

プログラミングでは、倍数の判定に使うことができます。

aはbの倍数かどうか?

a % b == 0

モジュロの数学的な性質

\((a \mod M) \mod M = a \mod M\)
\((M \cdot n) \mod M = 0\)
\((a \cdot b) \mod M = ((a \mod M) * (b \mod M)) \mod M\)
\((a + b) \mod M = ((a \mod M) + (b \mod M)) \mod M\)

9.1.1. 最大公約数¶

最大公約数(GCD)と最小公倍数(LCM)は、整数問題で頻出の概念です。

次の公式だけ覚えておけば、いつでも関数定義して作り出せます。

\(GCD(a, b) = GCD(b, a \mod b)\)
\(GCD(a, b)\cdot LCM(a, b) = ab\)

Let’s try

\(a > b\) のとき、最小公倍数を求めるLCM(a,b)を定義してみよう

[1]:

def GCD(a, b):
    if b == 0: return a
    return GCD(b, a % b)

def LCM(a, b):
    return a * b // GCD(a, b)

LCM(63,30)

[1]:

9.1.2. FizzBuzz問題¶

FizzBuzz 問題は，採用面接において、コードが書けないプログラマ志願者を見分ける手法としてJeff Atwood が提唱した有名問題です。

例題（FizzBuzz）

数字を１から順に１００まで発言します。ただし、

数字が３の倍数の時には数字の代わりにFizz
数字が５の倍数の時には数字の代わりにBuzz
数字が３の倍数かつ５の倍数の時には代わりにFizzBuzz

といいます。

[2]:

for i in range(1, 101):
    if i % 3 == 0 and i % 5 == 0:
        print("FizzBuzz", end=' ')
    elif i % 3 == 0:
        print("Fizz", end=' ')
    elif i % 5 == 0:
        print("Buzz", end=' ')
    else:
        print(i, end=' ')

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz

今では、色々な方法でコードを書くためのゲームになっています。

if文を使わないでFizzBuzzを書いてみた場合

[3]:

d = {15: 'FizzBuzz', 3: 'Fizz', 5: 'Buzz', 6: 'Fizz', 9: 'Fizz', 10: 'Buzz', 12: 'Fizz'}
for i in range(1, 101):
    print(d.get(i%15, i), end=' ')

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 15 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 30 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 45 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 60 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 75 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 90 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz

Let’s try

世の中には色々なFizzBuzzの書き方があります。調べてみましょう。

9.2. 素数¶

素数 (prime number) は、1 より大きい自然数で約数の個数が 2 である自然数です。

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,…

素数判定アルゴリズム

ある自然数 n が与えられたとき、n が素数かどうか判定するアルゴリズム

まず、定義通り約数の個数を数えることで、素数判定アルゴリズムを isPrime(n) と実装してみよう。

[4]:

def isPrime(n):
    count = 0
    for i in range(1, n+1):
        if n % i == 0: count +=1
    return count == 2

[5]:

isPrime(7)

[5]:

True

[6]:

isPrime (25)

[6]:

False

9.2.1. 少し効率を考えてみる¶

例題（素数の数）

1000,000以下の自然数には、素数がいくつあるか求めよ

isPrime(n) はあまり効率がよくありません。したがって、文字通りそのまま計算すると大変なことになります。

ものすごく時間がかかるので注意

[7]:

%%time
count = 0
for i in range(2, 10_000):
    if isPrime(i):
        count += 1
print(count)

1229
CPU times: user 2.71 s, sys: 8.21 ms, total: 2.72 s
Wall time: 2.73 s

isPrime(n)が遅い理由

\(n\) が大きくなると、計算時間がかかる \(O(n)\)
- 原理的に \(\sqrt{n}\) まで繰り返せば十分.
count が 2 より大きくなったら、素数ではないので繰り返す必要がない。

isPrime()の改良版

[10]:

def isPrime(n):
    count = 0
    for i in range(1, int((n+1)**0.5)+1):
        if n % i == 0:
            count +=1
            if count > 2:
                return False
    return count == 2

[11]:

%%time
count = 0
for i in range(2, 100_000):
    if isPrime(i):
        count += 1
print(count)

23392
CPU times: user 360 ms, sys: 2.05 ms, total: 362 ms
Wall time: 362 ms

9.3. エラトステネスのふるい¶

エラトステネスのふるいとは、古代ギリシア人が発明した素数のリストを作る効率のよいアルゴリズムです。高校数学でも登場するでも、原理は知っている人が多いでしょう。

エラトステネス

ドイツ語版ウィキペディアのSKoppさんによる作画

自然数の入ったふるい(篩, sieve)を考える
ふるいの中の一番小さな数を選ぶ. ** このとき、選ばれた数は素数となる. ** そして、この素数でリストの残りの数を割り、割り切れる数を消す。
この一連の操作を繰り返す. 最後までふるいに残った数が素数のリストとなる.

「エラトステネスのふるい」を実装する鍵は「データ表現」です。

Python には「ふるい型」はないので、既存のデータ型を使って「ふるい」をうまく表現する方法を考えます。素直に考えると、 sieve = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]のようにリストでふるい表現します。

[5]:

%%time
def eratosthenes(n):
    #まず 2からn未満の整数をふるい(sieve)に入れる
    sieve = list(range(2, n))
    for p in range(2, n): #小さい方から順番に古いの数字をみる
        if p in sieve: # sieveに残っていたら、pは素数
            for j in range(p * 2, n, p):  # p の倍数をすべてふるいから取り除く
                if j in sieve:
                    sieve.remove(j)
    return sieve

sum(eratosthenes(10_000))

CPU times: user 762 ms, sys: 2.53 ms, total: 765 ms
Wall time: 764 ms

[5]:

9.3.1. 効率を改善する鍵:データ表現¶

Python は便利なメソッドを提供しているので、リストから要素を取り除くことが簡単にできます。しかし、sieve.remove(n) を用いてリストから要素を取り除くのは \(O(n)\) で、効率がよくありません。

データ構造は重要

プログラミングは、データ構造の決め方で複雑さや性能が変わる.

ポイントは数がふるいに入っているかどうか?

エラトステネスのふるいでは、自然数 n がふるいの中に入っているか判定できればよいので、論理値 True, False を用いて判定することができる.

sieve[n] == True なら、n は「ふるい」の中
sieve[n] == False なら、n は「ふるい」の外
sieve[n] = False で、n をふるいから取り除く

[4]:

%%time

def eratosthenes(n):
    #まず 2からn未満の整数をふるい(sieve)に入れる
    sieve = [False, False] + [True] * (n-1)
    for p in range(2, n): #小さい方から順番に古いの数字をみる
        if sieve[p] == True: # sieveに残っていたら、pは素数
            for j in range(p * 2, n, p):  # p の倍数をすべてふるいから取り除く
                sieve[j] = False
    return sieve
sum(eratosthenes(10_000))

CPU times: user 2.26 ms, sys: 79 µs, total: 2.34 ms
Wall time: 2.35 ms

[4]:

9.3.2. 高速版: isPrime(n)¶

最後に高速な素数判定プログラムを紹介しておきます。（これは、さまざまなプログラムに活用できるテクニックです。）

[ ]:

sieve = eratosthenes(100_0000)

def isPrime(n):
    if n < 100_0000:
        return sieve[n]

ミラー–ラビン素数判定法（Miller–Rabin primality test）

乱択アルゴリズムによる素数判定アルゴリズム。素数かどうか確率的に高速に判定することができる。

9.4. 演習問題¶

数学的な性質に着目して解く問題を集めてみました。

課題リストより

トレーニング: モジュロの問題
105 N が小さいので安心してください
整数の選択
aとbの間
シュークリーム
完全数
次の素数
スナック
ボールの色塗り
黒板上の最大公約数
:math:`a^b <https://atcoder.jp/contests/abc193/tasks/abc193_c>`__
互いに素
モンスター
2019
2017-like Number: エラトステネスの篩

Python Programming 2021 ドキュメント