Project Euler with Ruby on WSL [Problem 3]

いつもどおり

ネタばれあり

問題文

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

私訳

600851475143 の素因数のうち最大のものはいくつか？

解答方針

とりあえず ということにして、 エラトステネスの篩的に まで素数リストを更新していく 試し割をして、割れてしまったら商のほうを試し割していく

解答

方針自体は単純だったがめちゃくちゃ手間取ってしまった… 高速化するために素数表を更新しながら試し割をして、 かつ添え字範囲を戻らないように…とかやっていただけなのに めちゃくちゃ時間がかかってしまった。雑魚い。

一応一般の素因数分解ができるはず

# Project Euler
# problem 3

# extend primes list
def extend_primes(list)
    cand = list.last
    begin
        cand+=2
        limit = Math.sqrt(cand)
        for j in 0...list.length
            p = list[j]
            if cand % p == 0
                break
            end
            if p > limit
                list.push(cand)
                return
            end
        end
    end while true
end

# [composition number], [list of primes]
# returns factorized list
# the first is the least prime factor, the last is the greatest.
# e.g. factorize([1024], [2,3,5,7])
#      => [2,2,2,2,2,2,2,2,2,2]
#      factorize([11311311], [2,3,5,7])
#      => [3, 11, 31, 11057]
def factorize(comp, primes)
    k = 0
    while true
        i = k
        target = Math.sqrt(comp.last)
        while i < primes.length
            p = primes[i]
            if p > target
                return comp
            end
            if comp.last % p == 0
                k = i # then, consider only primes[i] >= p
                q = comp.last / p
                comp.pop
                comp.push(p, q)
                target = Math.sqrt(q)
                next
            end
            i += 1
        end

        # primes.last tried, but cannot divide.
        k = i # then, consider only primes[i] > p
        extend_primes(primes) # extend list
    end
end

# the list of prime numbers
primes = [2, 3, 5, 7, 11]
c = [600851475143]
pp factorize(c, primes)