JuliaでProject Euler(7) - inamori’s diary

Problem 7

このあと単純にエラトステネスの篩を使う問題があるので、この問題はナイーブに素数判定するのが正しいと思われる。

Pythonでこう書く。

from itertools import *
import sys

def e007(N):
    primes = [2]
    
    def is_prime_naive(n):
        for p in primes:
            if p*p > n:
                return True
            elif n%p == 0:
                return False
    
    for n in count(3):
        if is_prime_naive(n):
            primes.append(n)
            if len(primes) == N:
                return n

N = int(sys.argv[1])
print e007(N)

Juliaにそのまま翻訳すると、

function e007(N)
    primes = [2]
    
    function is_prime_naive(n)
        for p in primes
            if p*p > n
                return true
            elseif n%p == 0
                return false
            end
        end
    end
    
    for n in Iterators.countfrom(3)
        if is_prime_naive(n)
            push!(primes, n)
            if length(primes) == N
                return n
            end
        end
    end
end

N = parse(Int, ARGS[1])
println(e007(N))

Arrayに要素を追加するのは、Arrayのメソッドではなくpush!関数を使う。ここで、!が付与されているのは破壊的な関数を示す。pushは無いようだが、例えばsortには2つバージョンがある。

julia> a = [3, 2]
2-element Array{Int64,1}:
 3
 2

julia> b = sort(a)
2-element Array{Int64,1}:
 2
 3

julia> a
2-element Array{Int64,1}:
 3
 2

julia> sort!(a)
2-element Array{Int64,1}:
 2
 3

julia> a
2-element Array{Int64,1}:
 2
 3

このように、sort!は自分を変えるが、sortは元のArrayは変えず、新たなArrayを作ってそれを返す。

上のコードを実行すると、

$ time julia e007a.jl 10000001
179424691

real    0m37.176s
user    0m37.078s
sys     0m0.656s
$ time pypy e007a.py 10000001
179424691

real    2m28.765s
user    2m28.141s
sys     0m0.484s

Juliaのほうが4倍速い。