2019-07-01から1ヶ月間の記事一覧

JuliaでProject Euler(18)

Problem 20 https://projecteuler.net/problem=20Problem16とだいたい同じ。Pythonで書くと、 from itertools import * import sys def multiply(v, n): v2 = [] carry = 0 for d in v: carry, r = divmod(d*n+carry, 10) v2.append(r) while carry > 0: car…

JuliaでProject Euler(17)

Problem 17 https://projecteuler.net/problem=17何度も解いているが、一度も最初で正しい答えを出した記憶がない。 できるだけ再帰を使う。 function e017(N) function num_length(n) if haskey(num_letters, n) && n < 100 return length(num_letters[n]) …

JuliaでProject Euler(16)

Problem 16 https://projecteuler.net/problem=16本当は速い方法(メルセンヌ数を10進表示する)があるが、ここでは単に2倍ずつしていく。Pythonでは、 import sys def twice(v): v2 = [] carry = 0 for d in v: carry, r = divmod(d*2+carry, 10) v2.append(r…

JuliaでProject Euler(15)

Problem 15 https://projecteuler.net/problem=15DPで解く。 function e015(N) a = zeros(Int, N+1, N+1) a[1,1] = 1 for x in 2:N+1 a[1,x] = 1 end for y in 2:N+1 a[y,1] = 1 end for y in 2:N+1 for x in 2:N+1 a[y,x] = a[y,x-1] + a[y-1,x] end end re…

JuliaでProject Euler(14)

Problem 14 https://projecteuler.net/problem=14Collatzはこう書ける。 function Collatz_length(n) len = 1 while n != 1 if n%2 == 0 n >>= 1 else n = n*3+1 end len += 1 end return len end function e014(N::Int) max_length, max_n = maximum((Colla…

JuliaでProject Euler(13)

Problem 13 https://projecteuler.net/problem=13多倍長整数を自作してもいいが、ここではBigIntを用いる。 function make_big_numbers() a = [ "37107287533902102798797998220837590246510135740250", "4637693767749000971264812489697007805041701826053…

JuliaでProject Euler(12)

Problem 12 https://projecteuler.net/problem=12本当は速い方法があるが、ここでは愚直に順番に約数の個数を調べていく。 function factorize_naive(n) fs = [] for d in Iterators.countfrom(2) if d*d > n break elseif n%d == 0 e = 1 n = div(n, d) whi…

JuliaでProject Euler(11)

Problem 11 https://projecteuler.net/problem=11generatorを使うと吉。 function make_table() a = [ "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08", "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00", "81 49 31 73 55 7…

JuliaでProject Euler(10)

Problem 10 https://projecteuler.net/problem=10エラトステネスの篩を行うだけ。 function make_prime_table(N::Int64) a = [ true for n in 1:N ] for p in 2:N if p*p > N break elseif !a[p] continue end for n in p*p:p:N a[n] = false end end return…

JuliaでProject Euler(9)

Problem 9 https://projecteuler.net/problem=9ピタゴラス数は一般に、と書ける(mとnは互いに素でどちらかが偶数で、)て、直角三角形の周囲の長さはとなるので、周囲の長さ/2を2つの約数に分けて、さらにその一方を2つの約数に分ける必要があるが、mとm+n…

JuliaでProject Euler(8)

Problem 8 https://projecteuler.net/problem=8 function make_table() a = [ "73167176531330624919225119674426574742355349194934", "96983520312774506326239578318016984801869478851843", "85861560789112949495459501737958331952853208805511", "125…

JuliaでProject Euler(7)

Problem 7 https://projecteuler.net/problem=7このあと単純にエラトステネスの篩を使う問題があるので、この問題はナイーブに素数判定するのが正しいと思われる。Pythonでこう書く。 from itertools import * import sys def e007(N): primes = [2] def is_…

JuliaでProject Euler(6)

Problem 6 https://projecteuler.net/problem=6 function e006(n) return sum(1:n)^2 - sum(k*k for k in 1:n) end N = parse(Int, ARGS[1]) println(e006(N)) 内包表記はPythonと同様に使える。べき乗は、**ではなく^を使う。PythonやCはXORを^に充てていた…

JuliaでProject Euler(5)

Problem 5 https://projecteuler.net/problem=5Pythonで次のように書く。 from fractions import gcd import sys def lcm(n, m): return n/gcd(n, m)*m def e005(n): return reduce(lcm, range(1, n+1), 1) N = int(sys.argv[1]) print e005(N) これをそのま…

JuliaでProject Euler(4)

Problem 4 https://projecteuler.net/problem=4Pythonで次のように書く。 import sys def digits(n): ds = [] while n > 0: n, r = divmod(n, 10) ds.append(r) return ds def is_palindromic(n): ds = digits(n) L = len(ds) return all(ds[k] == ds[L-k-1]…

JuliaでProject Euler(3)

Problem 3 https://projecteuler.net/problem=3Juliaで次のように書く。 function e003(n) local p = 2 while p*p <= n if n%p == 0 while true n = div(n, p) if n%p != 0 break end end if n == 1 return p else return e003(n) end end p += 1 end return…

JuliaでProject Euler(2)

Problem 2 https://projecteuler.net/problem=2Juliaで次のように書く。 function e002(N) local s = 0 local a = 1 local b = 1 while b <= N if b%2 == 0 s += b end a, b = b, a+b end return s end N = parse(Int, ARGS[1]) println(e002(N)) Pythonのタ…

JuliaでProject Euler(1)

JuliaでProject Euler(1)JuilaというPython対抗っぽい言語があるらしいので試してみる。 PyPyより速いらしい。 準備 ここからGeneric Linux Binaries for x86 64bit をダウンロード。https://julialang.org/downloads/ $ tar xvfz julia-1.1.1-linux-x86_64.…