# Euler Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

We can solve this reasonably quickly using a very basic algorithm for generating primes:

– 2 is prime

– a number is prime if it can’t be divided by any prime less than it

– so generate primes by looping and testing for divisibility against prime list

Code looks something like this:

require 'generator' def prime_gen() return Generator.new { |g| primes = [] n = 2 while 1 do prime = true for p in primes do if n%p == 0 then prime = false break end end if prime then primes << n g.yield n end n += 1 end } end g = prime_gen() for i in 1..10000 do g.next end puts g.next

While this code is fast enough for problem 7, this is not the last time we’ll see a problem requiring prime number generation; we’ll discuss optimizations in a later post.

## About this entry

You’re currently reading “Euler Problem 7,” an entry on blog

- Published:
- February 20, 2012 / 14:29

- Category:
- euler

- Tags:

## No comments yet

Jump to comment form | comment rss [?] | trackback uri [?]