エラトステネスの篩
sieve of Eratosthenes
10^7程度の大きさの数に対しても高速に動作する
ふるい落とす対象は途中でなくなる
区間の最大値の平方根で処理を止めることができる
区間におけるn番目の素数$ P_n における処理
新たに消去される最初の数は $ P_n \cdot P_nと表せる
これまでの処理で$ P_n \cdot P_{n-1}はすでに消去されているから
ふるい落とす処理が不要になる条件
新たに消去される数が区間の最大値$ M より大きい場合:
$ P_n \cdot P_n > M
ふるい落とす処理は$ P_n \le \sqrt{M} を満たす区間で行えばよい$ \square
findall()でインデックスを取れば数値の配列を扱わずにできる
2以降の偶数インデックスをあらかじめfalseにしておく？あんも.icon
code:jl
function primes(n::Int)
isprime = trues(n)
isprime1 = false # 1 is not a prime number for p in 2:floor(Int, sqrt(n))
for mult in p*p:p:n
end
end
end
return findall(isprime)
end
数値を扱う場合？あんも.icon
直接的だが計算は減ってなさそう
全数チェックになる
フラグの付け方がめんどう
要素の型があっていないといけない
code:jl
function primes(max_val::Int)
m = 1:max_val
sieve!(n, base) = (n == 1 || (n % base == 0 && n > base)) ? 0 : n # 篩処理関数
for base in 2:floor(Int, sqrt(max_val))
m = sieve!.(m, base)
end
return filter!(x -> x != 0, m)
end