Find the 10001st prime

In my last days in Porto, I was hopping around many cafés, and some were not so friendly towards computers; and I felt like taking a break from screens, anyway, so I bore some pen and paper to tackle these problems without, say, assisted computation.

Finding primes is an interesting problem. There are a few key ideas that I was already aware of:

— even numbers bigger than 2 are obviously not prime;

— for any number $n$, one can infer that its biggest divisor is limited.

but apparently there's another very useful trick, which almost derives from any prime not being divisible by two — but I'll leave that up, too. It should be easy to find out a general form that primes can be expressed in.

Given that I was solving in pen and paper, I should have derived an algorithm that implements the rules stated above; but I sort of cheated and when with prime?, which obviously simplifies matters further.

(import test)
(import (only (math number-theory)
			  prime?))

; tail-recursively iterates over odd integers until `count` amount of primes is reached
; returns the nth prime over 2 (we omit 2 to reduce half of the function calls by iterating over odd numbers)
; Integer -> Integer -> Integer
(define (nth-prime-over-2 i count n)
  (if (prime? i)
	(if (= count n)
	  i
	  (nth-prime-over-2 (+ i 2) (+ count 1) n))
	(nth-prime-over-2 (+ i 2) count n)))
(test 3 (nth-prime-over-2 3 1 1))
(test 13 (nth-prime-over-2 3 1 5))

;; retrieves the sum of the squares of naturals from 1 to (including) n
;; Integer -> Integer
(define (find-nth-prime n)
  (if (= n 1)
	2
	(nth-prime-over-2 3 1 (- n 1))))
(test 2 (find-nth-prime 1))
(test 3 (find-nth-prime 2))
(test 13 (find-nth-prime 6))


(define (solve-problem-7 n)
  (find-nth-prime n))

(print (solve-problem-7 10001))