裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

Julia で,ベクトル要素の全てと互いに素である整数のリストを求める

2021年08月21日 | ブログラミング

お題

ベクトル要素のそれぞれと互いに素である整数のリストを求める

ベクトル 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
=#

コメント    この記事についてブログを書く
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする
« Julia で円をモチーフにした... | トップ | Julia で,k 番目の順列を取... »
最新の画像もっと見る

コメントを投稿

ブログラミング」カテゴリの最新記事