お題
ベクトル要素のそれぞれと互いに素である整数のリストを求める
ベクトル a の全ての要素との gcd(最大公約数)が 1(つまり,互いに素)である m 以下の整数を列挙する。
例えば,
a = [4, 6] で,m = 20 のとき
a に含まれる数の約数は,2, 3 の2個
1 〜 20 までの数のうち,
2 で割りきれるものは,題意を満たさない(gcd は 2)。題意を満たすのは 1,3,5,7,9,11,13,15,17,19 の 10 個
そのうち,3 で割りきれるものは,題意を満たさない(gcd は 3)。題意を満たすのは 1, 5, 7, 11, 13, 17, 19 の 7 個
エラトステネスの篩と同じ考え方
1 〜 m の集合の内,既存の数の倍数(a の各要素の約数の集合)を全部潰していって,残ったのが解の集合ということ。
# 約数の候補
function divisor(n)
n % 2 == 0 && return 2
maxitr = floor(Int, sqrt(n))
for i = 3:2:maxitr
n % i == 0 && return i
end
n
end
# 約数の集合
function factorization(n)
result = []
while n > 1
div = divisor(n)
append!(result, div)
while n % div == 0
n ÷= div
end
end
result
end
# どの約数でも割りきれない数を残す
function f(n, m, a)
set = Set()
for i in a
union!(set, Set(factorization(i)))
end
lengthofset = length(set)
intvector = trues(m)
for i in set
maxindex = m ÷ i
for j = 1:maxindex
intvector[j*i] = false
end
end
println(sum(intvector .== true))
for (i, element) in enumerate(intvector)
if element
println(i)
end
end
end
a = [4, 6]
m = 20
f(length(a), m, a)
#=
7
1
5
7
11
13
17
19
=#
※コメント投稿者のブログIDはブログ作成者のみに通知されます