[ChatGPT] Python 学習 の 手助け (2) [他言語] (2/27)

1〜999まで全部の数を素因数分解したいというお題で、ChatGPTに問い合わせた結果が、これ。

def prime_factorization(n, spf):
    """spf (smallest prime factor) を使って素因数分解"""
    factors = {}
    while n > 1:
        p = spf[n]
        factors[p] = factors.get(p, 0) + 1
        n //= p
    return factors

def build_spf(limit):
    """各数の最小素因数を求める（高速）"""
    spf = list(range(limit + 1))
    for i in range(2, int(limit**0.5) + 1):
        if spf[i] == i:  # iが素数
            for j in range(i * i, limit + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

limit = 999
spf = build_spf(limit)

for i in range(1, limit + 1):
    if i == 1:
        print("1 = 1")
        continue
    
    factors = prime_factorization(i, spf)
    factor_str = " × ".join(
        f"{p}^{e}" if e > 1 else f"{p}"
        for p, e in sorted(factors.items())
    )
    print(f"{i} = {factor_str}")

Pythonの**0.5は累乗(二乗根)なので**(1/2)、つまり1/2乗。**0.5は√。ちなみに2**0.5=√2。

**(1/3)は立方根なので、2**(1/3)=3√2。3はルートの左上に乗る。3*√2の意味ではない。

これを実行すると、

1 = 1
2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 × 3
7 = 7
8 = 2^3
9 = 3^2
10 = 2 × 5
11 = 11
12 = 2^2 × 3
13 = 13
14 = 2 × 7
15 = 3 × 5
16 = 2^4
17 = 17
18 = 2 × 3^2
：
999 = = 3^3 × 37

■ C言語で書くと、

#include <stdio.h>

void build_spf(int limit, int spf[]) {
  for (int i = 0; i <= limit; i++)
    spf[i] = i;

  for (int i = 2; i * i <= limit; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j <= limit; j += i) {
        if (spf[j] == j)
          spf[j] = i;
      }
    }
  }
}

void prime_factorization(int n, int spf[]) {
  while (n > 1) {
    int p = spf[n];
    int count = 0;

    while (n % p == 0) {
      n /= p;
      count++;
    }

    if (count == 1)
      printf("%d", p);
    else
      printf("%d^%d", p, count);

    if (n > 1)
      printf(" × ");
  }
}

int main() {
  int limit = 999;
  int spf[1000];

  build_spf(limit, spf);

  for (int i = 1; i <= limit; i++) {

    if (i == 1) {
      printf("1 = 1\n");
      continue;
    }

    printf("%d = ", i);
    prime_factorization(i, spf);  // iがそれ以下の素数で因数分解できるか
    printf("\n");
  }

  return 0;
}

うん。

難しく感じるのはエラトステネスのふるいの部分だ。

つまり、spf[]は何のためにどんな値が入っているかという事。

C言語で調べると、

spf[0] = 0

spf[1] = 1

spf[2] = 2

spf[3] = 3

spf[4] = 2

spf[5] = 5

spf[6] = 2

spf[7] = 7

spf[8] = 2

spf[9] = 3

spf[10] = 2

spf[11] = 11

spf[12] = 2

spf[13] = 13

spf[14] = 2

spf[15] = 3

spf[16] = 2

：

となる。

最初に割り切れる数が入っているようだ。

そして使い方としては、

void prime_factorization(int n, int spf[]) {
  while (n > 1) {
    int p = spf[n];
    int count = 0;

となっており、

ここは注意すべき点として、【while文の中の自動変数の宣言時の代入】だ。

whileループ内で自動変数（ローカル変数）を宣言し、同時に代入（初期化）を行う場合、その変数はループが1回実行されるたびに生成・破棄され、{}内で、毎回初期化(代入)されるのだ。

(変数の宣言と同時に初期値が代入されるから、intの付かないただの代入文とは違い、毎回破棄される)

void prime_factorization(int n, int spf[]) {
  while (n > 1) {
    int p = spf[n];  // p はループ内で毎回初期化(ただし、n が関数内で変化するので、spf[0],spf[1]...と変化する
    int count = 0;   // count もループ内で毎回初期化

    while (n % p == 0) {
      n /= p;        // n は関数の引数だが値をスタック上に持っており、書換えてワーク変数として使っている

となっており、

C言語の、目立たないが重要な仕様を、テクニック的に使っている。

(通常はループ外の関数の自動変数にして代入だけ行う。宣言までループ内にすると正しいが、変数のスコープの管理を注意しないとバグの原因になる。例えばループ外で参照しようとするとかグローバル変数に同名の変数があったりする等)

※ 関数内の最初で自動変数を使うのは変数の局所化で正しいが、{}内で宣言する事を許すと、変数が散在する事になり、局所化とは逆になってしまう。{}内は本当に本当のワーク変数だけに使うべきだ。

この辺はC++のクラス内変数(コンストラクタ等)が影響しているのだろう。

うまい方法だが、注意が必要だ。

で、この関数は、自分の中でprint文を持っており、spf[]を複数回関数内で参照している。

エラトステネスのふるいで、√まで調べればよいというのはわかるが、その後の素因数分解をこの関数は実行している。

6ならば、ループ内で

n=6,p=2

n=3,p=3

となり、2×3と出力する。

nが更新される点がポイントで、それに従い参照するspf[]の値も変わってくる。

spfテーブルを、自分の値(6)のテーブルから徐々に小さいテーブル(3)へと下っていく。

それによって『因数』分解しているのだ。

下る途中で素数のテーブル(例えば14ならn=14,7と下っていく)があれば『素因数』として分解される。

因数：ある整数を割って複数の整数になる場合、その整数を因数と呼び、元の整数を合成数と呼ぶ。

C言語でこの関数のふるまいを理解すれば、Pythonでそれを実現するにはどう書けばいいかわかる。

Googleで"エラトステネスのふるい 最小素因数を求める（高速）"で検索すると、osa_k 法という名前で有名らしい。

高速化するなら、Cだとさらにpやcountをスタックに置くのではなくグローバルにし、mainのspfもグローバルに置くのが良いだろう。

コンパイラがスタックをレジスタに置いてくれるのならp,countはmainのspfと同じレベルのスタックに置いて、関数呼び出し毎に生成・消滅を繰り返さない方が良い。そしてspfは大規模なテーブルになるのでグローバルに移動した方がいい。

突き詰めるなら、多倍長整数の配列の格納場所・アクセス方法をCやアセンブラで、多倍長整数の演算をGPUに任せた方がいい。