logo

素因数分解 📂整数論

素因数分解

コード

R

次に、Rコードで実装されたエラトステネスの篩である。自然数$n$が与えられると、エラトステネスの篩と同じ方法で素数かどうかを判断してくれる。$n$そのものが返されれば素数で、$n$より小さい数が返されれば、それは$n$の約数の中で最小の数を意味する。

eratosthenes<-function(n){
  residue<-2:n
  while(n %in% residue){
    p<-residue[1]
    residue<-residue[as.logical(residue%%p)]
  }
  return(p)
}
 
eratosthenes(101)
eratosthenes(1517)

20190807\_144554.png 例えば、$101$は素数なので、$101$がそのまま返され、$1517=37 \times 41$なので、$37$が返される。

ジュリア

以下はもっと効率的に実装されたジュリアコードである。

function factorize(n)
    factors = []
    while n > 1
        for k in 2:n
            if n % k == 0
                n ÷= k
                push!(factors, k)
            end
        end
    end
    return factors
end

function eratosthenes(n::Integer)
    if n == 1 return [[1]] end
    if n == 2 return [[1], [2]] end
    primes = [2]
    factorized = [[1], [2]]
    for k ∈ 3:n
        m = k
        for p ∈ primes
            if m % p == 0
                m ÷= p
                temp = [p; factorized[m]]
                push!(factorized, temp)
                break
            end
        end
        if length(factorized) != k
            push!(primes, k)
            push!(factorized, [k])
        end
    end
    return factorized, primes
end
F, P = eratosthenes(20)
F
P

一緒に見る

素因数分解問題の難しさを利用したセキュリティアルゴリズム

素因数分解問題に対する攻撃アルゴリズム