Skip to content

Instantly share code, notes, and snippets.

@tcdowney

tcdowney/primeperms.rb

Forked from baweaver/primeperms.rb
Last active August 29, 2015 14:00
Show Gist options
  • Save tcdowney/11164674 to your computer and use it in GitHub Desktop.
Save tcdowney/11164674 to your computer and use it in GitHub Desktop.
Download ZIP
Use the sieve :)
Raw
primeperms.rb
def eratosthenes(n)
nums = [nil, 1, *2..n]
(2..Math.sqrt(n)).each do |i|
(i**2..n).step(i){|m| nums[m] = nil} if nums[i]
end
nums
end
primes_to_million = eratosthenes(1_000_000)
prime_perms = primes_to_million.select { |n|
n.to_s
.chars
.permutation
.flat_map(&:join)
.map(&:to_i)
.all?{ |n| primes_to_million[n] }
}.count
puts prime_perms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment