0

I'm trying to find a way to find the 10001th prime number for project euler #7, I've already brute forced my way to find the answer but I would much prefer to know how to reach the answer with more sophisticated methods that are much quicker to run. Please do explain to me in detail how it works.

I know it all methods require math, so my main concern is understanding the mathematical logic behind the solution to finding the nth prime.

aimen alt
  • 102
  • 8
  • If someone doesn't provide an answer you might have better luck in one of the more sciency Stack Exchange websites. Computer Science could be a good fit. See here: https://meta.stackexchange.com/questions/165519/where-should-i-post-questions-about-algorithms-stack-overflow-or-software-engin – Casper Aug 14 '18 at 22:01
  • Thanks @Casper, I'll definitely be checking those site as well. – aimen alt Aug 14 '18 at 22:59
  • @m69 Not Duplicate, I've already seen it but it turned out it was using java not ruby. – aimen alt Aug 14 '18 at 23:00
  • Well, the maths is the same, and "my main concern is understanding the mathematical logic behind the solution". – m69's been on strike for years Aug 14 '18 at 23:13
  • 1
    I'm gonna go with the dupe as well...looks like a pretty detailed explanation, and glancing through the code there doesn't appear to be anything super java-y in any of the blocks...it shouldn't take any significant amount of time or effort to convert the code to ruby...and if there is something that doesn't translate easily we can always help with "here's a line of java code and I'm having trouble figuring out how to do it in ruby"...I see a fair number of questions like that pop up – Simple Lime Aug 14 '18 at 23:30
  • Are you asking if there is a way to obtain the 10,001st prime without first computing the first 10,000 primes? See this [Wiki](https://en.wikipedia.org/wiki/Generating_primes). – Cary Swoveland Aug 15 '18 at 00:29

2 Answers2

2

The nth prime is less than n(loge n + loge loge n), as any number theory textbook will tell you, so you can use the Sieve of Eratosthenes to compute too-many primes, then trim the list to the desired size. Here's a simple version of the Sieve of Eratosthenes:

function primes(n) # primes less than n
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] = False

For the 10,000th prime, you will need the primes less than 10000 * (log 10000 + log log 10000) = 10000 * (9.21034 + 2.2203268) = 114307. Your sieve should compute the list of primes and return instantly. I'll leave it to you to translate that pseudocode to Ruby.

There are better ways to compute the nth prime number, but this is sufficient for Project Euler, and will be much faster than using trial division to check numbers for primality.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • 1
    Of course, you could also do `require 'prime'; Prime.lazy.drop(10000).first` (or `Prime.take(10001).last`) as a *much* faster alternative :P On the plus side: pure Ruby, no Java. On the minus side: you learn nothing about maths. – Amadan Aug 15 '18 at 06:18
0

Here is an example (and one of the very few moments I think it's okay to use a global variable).

$primes = {2 => nil}  # Hash for constant asymptotic lookup time, 2 for only even prime

def prime?(num)
  return false if num <= 1
  return true if $primes.key?(num)
  Math.sqrt(num).to_i.downto(2).each {|i| return false if num % i == 0}
  $primes[num] = nil
  true
end

num = 3  # start with first odd prime
while ($primes.length < 10001)
  prime?(num)  #  Check if number is prime and add to $primes if it is
  num += 2     #  Only check odd numbers
end

$primes.keys[1-1]      # 1st prime number => 2
$primes.keys[10001-1]  # 10001st prime number => 104743

In this example line return true if $primes.key?(num) is not needed, but it's useful when checking a number that is already known to be prime. I hope you find this helpful.

wteuber
  • 1,208
  • 9
  • 15
  • "(and one of the very few moments I think it's okay to use a global variable)" - Why? The whole thing could have been wrapped inside a function to make `primes` local to the outer function, with no loss of functionality, while avoiding polluting the global namespace. – Amadan Aug 15 '18 at 06:46
  • I totally agree! I would not create lib or app code that contains a global variable, but I liked the idea of prime numbers being available globally because of there fundamental nature. So, in this example it's (not great or nice but) "okay" for me :-) – wteuber Aug 15 '18 at 08:21