joshuaclayton/sieve — Issue #1: Feature Request: Euler totient phi sieve
Author: kentor
Created: 2012-01-10 13:32:18+00:00
State: open

How about a sieve for the Euler totient function? Something along the lines of

def phi_sieve(limit)
sieve = (0..limit).to_a
sieve.each_with_index do |p,i|
next if p != i || i < 2
break if 2*p > limit
p.step(limit, p) { |n| sieve[n] = sieve[n] / p * (p-1) }
end
sieve
end