largest prime product


Write a function that accepts a positive integer and returns the largest product of two primes less than the input value. The linear (more or less) solution fails one test. Unfortunately, my ability to fix the problem ran out before my patients with this problem did.

For extra fun, misread the problem and write linear (more or less) code to find the largest prime product that's at most the input value. Then realize your mistake and change your code to solve the problem as given. If you're as dumb as me, the change between "at most" and "less than" is murderous.

Also, there are lots of little tricks to be found that make the code fractionally faster, the most obvious one being counting down from n instead of counting up from 1.

 $ cat lpp.rkt 
 #lang racket 
  
 (require rackunit srfi/1) 
  
 (define (fold-over-products n mxp products) 
   (fold 
     (lambda (pp mx) (if (and (> pp mx) (< pp n)) pp mx)) 
     mxp products)) 
  
  
 (define (largest-prime-at-most n) 
  
   ; Return the largest prime that's at most the given value. 
    
   (let* 
     ((p-seq (set-prime-sequence n)) 
      (i (vector-insertion-index n p-seq))) 
  
     (if (> i 0) 
       (vector-ref p-seq (- i 1)) 
       (error "no largest prime at most" n)))) 
  
  
 (define (lpp n) 
  
   ; Return the largest product of two primes that's less than the 
   ; given value. 
  
   (fold-over-products n 0 
     (map 
       (lambda (p) (* p (largest-prime-at-most (quotient n p)))) 
       (primes-at-most (quotient n 2))))) 
  
  
 (define (lpp-nsq n) 
  
   ; Return the largest product of two primes that's less than the 
   ; given value. 
  
   (let loop ((primes (primes-at-most n)) (max-pp 0)) 
     (if (null? primes) 
       max-pp 
       (loop (cdr primes) 
         (fold-over-products n max-pp 
         (let ((prime (car primes))) 
           (map (lambda (p) (* prime p)) primes))))))) 
  
                
 (define (primes-at-most n) 
  
   ; Return in ascending order the list of primes that are at most n. 
  
   (let ((p-seq (set-prime-sequence n))) 
     (vector->list 
       (vector-take p-seq (vector-insertion-index n p-seq))))) 
  
           
 (define (set-prime-sequence n) 
  
   ; Return in ascending order the list of primes that are at most n. 
    
   (define (make-seive) 
     (let ((seive (make-vector (+ n 1) #t)) 
      (mx (quotient n 2))) 
       (let loop ((i 2)) 
         (if (>= i mx) 
           seive 
           (begin 
             (when (vector-ref seive i) 
               (do ((j (* 2 i) (+ j i))) ((> j n)) 
                 (vector-set! seive j #f))) 
             (loop (+ i 1))))))) 
  
   (define (make-prime-sequence seive) 
     (filter 
       (lambda (v) (> v 1)) 
       (map 
         (lambda (f v) (if f v 0)) 
         (vector->list seive) (iota (vector-length seive))))) 
  
   (when (> n prime-sequence-limit) 
     (set! prime-sequence 
       (list->vector (make-prime-sequence (make-seive)))) 
     (set! prime-sequence-limit n)) 
  
   prime-sequence) 
  
  
 (define (vector-insertion-index n vec) 
  
   ; Return the leftmost (smallest) index at which the given value 
   ; would be inserted into the ascending value vector. 
  
   (let loop ((l 0) (r (vector-length vec))) 
     ; vec[0..l) <= n < vec[r..N) 
     (if (= l r) 
       l 
       (let ((m (quotient (+ l r) 2))) 
         (if (<= (vector-ref vec m) n) 
           (loop (+ m 1) r) 
           (loop l m)))))) 
  
  
 (define prime-sequence-limit 2) 
 (define prime-sequence #(2)) 
  
 (check-eq? (car (reverse (primes-at-most 7))) 7) 
 (check-eq? (car (reverse (primes-at-most 8))) 7) 
  
 (define (test-it f) 
   (for-each 
     (lambda (n pp) (check-eq? (f n) pp (format "n = ~v" n))) 
     '(5 6 10 14 20 21 30 40 49 50 60 62 70 80 90 100 129 278)   ; n 
     '(4 4  9 10 15 15 26 39 46 49 58 58 69 77 87  95 123 274))) ; (f n) 
  
 (test-it lpp) 
 (test-it lpp-nsq) 
  
 (when #t 
   (do ((i 5 (+ i 1))) ((> i 1000)) 
     (check-eq? (lpp i) (lpp-nsq i) (format "i = ~v" i)))) 
  
  
 $ mzscheme lpp.rkt 
 -------------------- 
 FAILURE 
 actual:     0 
 expected:   4 
 name:       check-eq? 
 location:   (#<path:/mnt/projects/programming-problems/scheme/lpp.rkt> 130 19 3069 40) 
 expression: (check-eq? (f n) pp) 
 message:    "n = 6" 
  
 Check failure 
 -------------------- 
 -------------------- 
 FAILURE 
 actual:     0 
 expected:   4 
 name:       check-eq? 
 location:   (#<path:/mnt/projects/programming-problems/scheme/lpp.rkt> 139 4 3333 51) 
 expression: (check-eq? (lpp i) (lpp-nsq i)) 
 message:    "i = 6" 
  
 Check failure 
 -------------------- 
  
 $