Skip to content

Instantly share code, notes, and snippets.

@esehara esehara/atkin.rb
Last active May 19, 2018

Embed
What would you like to do?
アトキンのふるい
class SieveHelper
def initialize(limit, x, y)
@limit = limit
@x = x
@y = y
end
def invalid?
(@x ** 2) + (@y ** 2) >= @limit
end
def first_formula
(4 * @x ** 2) + (@y ** 2)
end
def first_check?
n = first_formula
n <= @limit && (n % 12 == 1 || n % 12 == 5)
end
def puts_first_formula
puts "#{first_formula}, x = #{@x}, y = #{@y}"
end
def second_formula
(3 * @x ** 2) + (@y ** 2)
end
def second_check?
n = second_formula
n <= @limit && (n % 12 == 7)
end
def puts_second_formula
puts "#{second_formula}, x = #{@x}, y = #{@y}"
end
def third_formula
(3 * @x ** 2) - (@y ** 2)
end
def third_check?
n = third_formula
n <= @limit && @x > @y && (n % 12 == 11)
end
def puts_third_formula
puts "#{third_formula}, x = #{@x}, y = #{@y}"
end
end
def sieve_flag!(sieve, limit)
# 平方根を取る
# => これはエラトステネスの場合も一緒である
sqrt_limit = Math.sqrt(limit).ceil
1.upto(sqrt_limit) do |x|
1.upto(sqrt_limit) do |y|
h = SieveHelper.new(limit, x, y)
next if h.invalid?
if h.first_check?
n = h.first_formula
# h.puts_first_formula
sieve[n] = !sieve[n]
end
if h.second_check?
n = h.second_formula
# h.puts_second_formula
sieve[n] = !sieve[n]
end
if h.third_check?
n = h.third_formula
# h.puts_third_formula
sieve[n] = !sieve[n]
end
end
end
return sieve
end
def delete_if_multiple(sieve, limit)
# それぞれの倍数も消す
for n in 5..limit do
if (sieve[n])
x = n ** 2
x.step(limit, x) {|i| sieve[i] = false }
end
end
return sieve
end
def atkin(limit)
# 結果を格納する配列を初期化する
sieve = Array.new(limit)
# 2, 3は素数であるので、ハードコーディングする
sieve[2] = true
sieve[3] = true
return delete_if_multiple(
sieve_flag!(sieve, limit),
limit)
end
atkin(100).each_with_index {|x, i| print " #{i}" if x}
puts ""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.