Juliaでエラトステネスの篩をやってみる

julia

rustでエラトステネスの篩を実装したので、今回はjuliaで実装していきます

rustで実装した様子はこちら

エラトステネスの篩については、rustの記事をよむなり、ググるなりしてね。

Juliaでエラトステネスの篩を実装

Juliaでの実装も基本はrust版と一緒です。

篩の実装

篩の実装していきましょう

関数名はsieve_composite_number

引数は1からnまでの数列と素数を受け取ります。

function sieve_composite_number(nums,primie_number)
    idx = primie_number
    while idx <= length(nums)-primie_number
        idx += primie_number
        nums[idx]=0
    end
    return nums
end

juliaの場合は、配列のインデックスは1から始まるので、何の小細工もなく進めていけます。

作業としては地味だねー

一個一個消していくっていうね

素数の割り出しと繰り返し

素数を見つけてそれを\(sqrt(n)\)まで繰返す操作を実装します。

    last_num = end_num|>sqrt|>floor
    idx = 0
    while idx< last_num
        idx+=1
        if nums[idx]!=0
            nums = sieve_composite_number(nums,idx)
        end
    end

素数リストの作成

素数のリストを作成していきます。

0が入ったものは素数ではない合成数なので、それ以外を拾っていきます。

    prime_numbers =[]
    for i in eachindex(nums)
        if nums[i]!=0
            push!(prime_numbers,nums[i])
        end
    end

n以下の素数を返す関数を作る

それでは、組み合わせて、n以下の素数を返す関数を作っていきます

関数名はget_prime_numbers

function get_prime_numbers(end_num)
    nums = [n for n = 1:end_num]
    nums[1]=0
    
    last_num = end_num|>sqrt|>floor

    idx = 0
    while idx< last_num
        idx+=1
        if nums[idx]!=0
            nums = sieve_composite_number(nums,idx)
        end
    end

    prime_numbers =[]
    for i in eachindex(nums)
        if nums[i]!=0
            push!(prime_numbers,nums[i])
        end
    end
            
return prime_numbers

end

最初に1からnまでの素数の配列を作ってます。

リスト内包表記で書けば一行でかけてすっきりー

まとめ

エラトステネスの篩のjulia版も作ってみました。

アルゴリズムっていうか実装のしかたは、rust版とほぼ一緒です。

juliaってc言語なみに早いっていうし、どれぐらいのスピードが出るか楽しみー

コメント

タイトルとURLをコピーしました