整数問題 ３ 題（その2）

久しぶりに AWK（GAWK）で書いてみた。

やはり R で書くとすっきり書ける。

$ cat prog.awk
#!/usr/local/bin/gawk -f
function F(term,    a, b, c, n, count, d) {
  a = 3
  b = 0
  c = 2
  count = 1
  for (n = 3; ; n++) {
    d = a+b
    if (d % n == 0 && ++count == term) return d
    a = b
    b = c
    c = d
  }
}

function divisor(n,     i) {
  if (n % 2 == 0) return 2
  else if (n % 3 == 0) return 3
  maxitr = int(sqrt(n))
  for (i = 5; ; i += 4) {
    if (i > maxitr) return n
    else if (n % i == 0) return i
    i = i + 2
    if (i > maxitr) return n
    else if (n % i == 0) return i
  }
}

function G(n,     d) {
  for (;;) {
    d = divisor(n)
    n = n/d
    if (n == 1) return d
  }
}
 
function H(n,     i, tbl, j, prime, sum) {
  for (i = 1; i <= n; i++) {
    tbl[i] = i
  }
  tbl[1] = 0
  for (i = 2; i <= int(sqrt(n)); i++) {
    if (tbl[i]) {
      for (j = 2; j <= int(n / i); j++) {
        tbl[j*i] = 0
      }
    }
  }
  for (i = 1; i <= n; i++) {
    if (tbl[i] > 0) {
      prime[++count] = tbl[i]
    }
  }
  for (i = 1; i <= count; i++) {
    if (prime[i] <= count) {
      sum += prime[prime[i]]
    }
  }
  return sum
}

BEGIN {
  P = F(30)
  Q = G(P)
  R = H(Q)
  printf "P = %i, Q = %i, R = %i\n", P, Q, R
}

$ time ./prog.awk
P = 63088012960224, Q = 120739, R = 72834276
0.132u 0.005s 0:00.13 100.0%    0+0k 0+0io 0pf+0w

模範解答としてはどうかなあ

素因数分解なんだけど

> 対象の数を、まずは2でこれ以上割り切れなくなるまで割り尽くします。
> 次にその商を3で割り尽くします。
> さらにその商を4,5,6,・・・の順で割りつくしていけば...

4 や 6... で割ることを試みるのは，無駄だと知らない訳か？

5 以上の素数は 6n±1 （n = 1, 2, ...）で表すことができる。しかし，6n±1 が必ず素数であるとは限らない（25 や 49）。

さらには，模範解答には書いていないのだけど，調べる約数はどこまでにするか。
模範解答氏は，「対象の数-1」まで調べてしまいそう（藁）。