素因数分解
コード
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)
例えば、$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