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

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

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

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

Juliaでエラトステネスの篩を実装
1. 篩の実装
2. 素数の割り出しと繰り返し
素数リストの作成
1. ｎ以下の素数を返す関数を作る
まとめ

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

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

篩の実装

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

関数名はsieve_composite_number

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

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

素数リストの作成

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

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

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

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

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

関数名は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からｎまでの素数の配列を作ってます。

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