45 lines
1.1 KiB
Crystal
45 lines
1.1 KiB
Crystal
require "bit_array"
|
|
|
|
def count_primes(n : Int64)
|
|
if n < 3_i64
|
|
return 0_i64 if n < 2_i64
|
|
return 1_i64
|
|
end
|
|
rtlmt = Math.sqrt(n.to_f64).to_i32
|
|
mxndx = (rtlmt - 3) // 2
|
|
cmpsts = BitArray.new(mxndx + 1)
|
|
i = 0
|
|
while true
|
|
c = (i + i) * (i + 3) + 3
|
|
break if c > mxndx
|
|
unless cmpsts[i]
|
|
bp = i + i + 3
|
|
until c > mxndx
|
|
cmpsts[c] = true
|
|
c += bp
|
|
end
|
|
end
|
|
i += 1
|
|
end
|
|
oprms = Array(Int32).new(cmpsts.count { |e| !e }, 0)
|
|
pi = 0
|
|
cmpsts.each_with_index do |e, i|
|
|
unless e
|
|
oprms[pi] = (i + i + 3).to_i32; pi += 1
|
|
end
|
|
end
|
|
phi = uninitialized Proc(Int64, Int32, Int64) # recursion target!
|
|
phi = ->(x : Int64, a : Int32) {
|
|
return x - (x >> 1) if a < 1
|
|
p = oprms.unsafe_fetch(a - 1)
|
|
return 1_i64 if x <= p
|
|
phi.call(x, a - 1) - phi.call((x.to_f64 / p.to_f64).to_i64, a - 1)
|
|
}
|
|
phi.call(n, oprms.size) + oprms.size
|
|
end
|
|
|
|
start_time = Time.monotonic
|
|
(0 .. 9).each { |i| puts "π(10**#{i}) = #{count_primes(10_i64**i)}" }
|
|
elpsd = (Time.monotonic - start_time).total_milliseconds
|
|
|
|
puts "This took #{elpsd} milliseconds."
|