Maximum Product Of Two Primes Less Than N: Racket and C++

Maximum product less than n of two primes

Racket

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. #lang racket
2.  
3. ;;http://programmingpraxis.com/2015/08/28/maximum-product-of-two-primes-less-than-n/
4.  
5.  
6. (require data/bit-vector)
7.  
8. (define (sieve limit)
9.   (define bv (make-bit-vector (+ limit 1) #f))
10.   (bit-vector-set! bv 0 #t)
11.   (bit-vector-set! bv 1 #t)
12.   (for* ([i (in-range (add1 (sqrt limit)))] #:unless (bit-vector-ref bv i)
13.          [j (in-range (* 2 i) (bit-vector-length bv) i)])
14.     (bit-vector-set! bv j #t))
15.   ;; translate to a list of primes
16.   (for/list ([i (bit-vector-length bv)] #:unless (bit-vector-ref bv i)) i))
17.  
18.  
19.  
20. (define (max-prod-prime n)
21.   (define primes (sieve (quotient n 2)))
22.   (define rprimes (reverse primes))
23.   (define (iter ps rps maxa maxb)
24.     (let* ([a (car ps)]
25.            [helper-p (lambda (x) (> x (quotient n a)))]
26.            [nrps (dropf rps helper-p)]
27.            [b (car nrps)])
28.       (if (> a b)
29.           (values (* maxa maxb) maxa maxb)
30.           (if (> (* a b) (* maxa maxb))
31.               (iter (cdr ps) nrps a b)
32.               (iter (cdr ps) nrps maxa maxb)))))
33.   (iter primes rprimes 0 0))

C++ (Sieve Omitted)

Data hosted with ♥ by Pastebin.com - Download Raw - See Original

1. #include <iostream>
2. #include <vector>
3. #include <inttypes.h>
4. #include <cmath>
5.  
6. //compile on osx: clang -lstdc++ ./erato.cpp -o erato
7. //compile on cygwin clang++ -lgmp -lstdc++ ./erato.cpp -o erato
8.  
9. //sieve and main omitted
10.  
11. uint64_t maximum_prime_product(uint64_t limit)
12. {
13.   std::vector<uint64_t> primes = primes_to(limit/2);
14.   uint64_t i = 0;
15.   uint64_t j = primes.size() - 1;
16.   uint64_t max_product = 0;
17.   while (i <= j)
18.     {
19.     while ((primes[i] * primes[j]) > limit)
20.       {
21.     j--;
22.       }
23.     if ((primes[i] * primes[j]) > max_product)
24.       max_product = primes[i] * primes[j];
25.     i++;    
26.     }
27.   return max_product;
28. }