Euler Project 58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31

38 17 16 15 14 13 30

39 18  5  4  3 12 29

40 19  6  1  2 11 28

41 20  7  8  9 10 27

42 21 22 23 24 25 26

43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13  62%.
If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

My Solution

(defun  primep (n)

        (cond ((minusp n) 'nil)

                  ((= 2 n) t)

                  ((evenp n) 'nil)

                  ((= 1 n) 'nil)

                  (t (let ((limit (floor (sqrt n))))

                      (do ((i 3 (incf i 2)))

                            ((> i limit) t)

                            (if (= 0 (mod n i)) (return-from primep 'nil)))))))

(defun Euler58(n)

  (let ((tempvar 0)

         (square 0)

         (spiralstep 0))

    (loop for i from 3 to n by 2

        do(progn (setq square (* i i))

                     (setq spiralstep (- i 1))

     (if (primep square)
         (incf tempvar))
     (if (primep (- square spiralstep))
         (incf tempvar))
     (if (primep (- square spiralstep spiralstep))
         (incf tempvar))
     (if (primep (- square spiralstep spiralstep spiralstep))
         (incf tempvar))
     (if (< (/ tempvar (- (* 2 i) 1.0))
             0.1)
         (return i))))))

Others' Solution

First Solution(I do not want to change the format, I will check the solution on the ProjectEuler)

(defun euler058 ()
(spiral-outwards 1000000000))
  

(defun spiral-outwards (bound)
(iterate loop ((number-of-diagonals 5)
(number-of-primes 3)
(side 3)
(dne 3)
(dsw 7)
(dnw 5)
(linear-term 8))
(if (< (/ number-of-primes number-of-diagonals) 1/10)
(cons side (/ number-of-primes number-of-diagonals))
(let ((new-dne (+ dne linear-term 2))
(new-dsw (+ dsw linear-term 6))
(new-dnw (+ dnw linear-term 4)))
(if (>= (max new-dne new-dsw new-dnw) bound)
(error "Too big for primeality test!")
(let ((new-primes (count-if #'(lambda (p) (prime-p p))
(list new-dne new-dsw new-dnw))))
(loop (+ number-of-diagonals 4)
(+ number-of-primes new-primes)
(+ side 2)
new-dne
new-dsw
new-dnw
(+ linear-term 8))))))))
  

(defun prime-p (n)
(unless (< n 25000000000)
(error "primality-by-millers-test: invalid for n >= 25000000000"))
(cond ((< n 2047)
(millers-test n 2))
((< n 1373653)
(and (millers-test n 2) (millers-test n 3)))
((< n 25326001)
(and (millers-test n 2) (millers-test n 3) (millers-test n 5)))
(:else
(and (/= n 3251031751) (millers-test n 2)
(millers-test n 3) (millers-test n 5) (millers-test n 7)))))
 

 (defun millers-test (n b)
(let ((n-1 (1- n)))
(multiple-value-bind (s m) (factor-out-2s n-1)
(let ((z (exp-mod b m n)))
(if (or (= z 1) (= z n-1))
t
(do ((j 1 (1+ j))
(z (exp-mod z 2 n) (exp-mod z 2 n)))
((>= j s) nil)
(if (= z n-1)
(return-from millers-test t))))))))

(defun factor-out-2s (n)
(iterate loop ((m n)
(s 0))
(multiple-value-bind (q r) (floor m 2)
(if (= r 1)
(values s m)
(loop q (1+ s))))))
 

 (defun exp-mod (base power modulus)
(iterate loop ((res 1)
(n power)
(a base))
(if (plusp n)
(loop (if (oddp n) (mod (* a res) modulus) res)
(ash n -1)
(mod (* a a) modulus))
res)))

Second Solution

(loop
for side = 0 then (if (= side 3) 0 (1+ side))
for size = 3 then (if (zerop side) (+ 2 size) size)
for no = 3 then (+ (1- size) no)
count (primep no) into primes
count no into total
until (and (zerop side) (<= (/ primes total) 1/10))
finally (return (- size 2)))