## Maximum Product Of Two Primes Less Than N

### August 28, 2015

The solution is a variant of the “crossing pointers” algorithm of a previous problem: create pointers to the two ends of a list of the primes less than half of *n*, then loop, increasing the left pointer if the product is less than the current maximum, decreasing the right pointer if the product exceeds *n*, and resetting the current maximum whenever a new maximum is found, reporting a result when the two pointers cross:

(define (max-prod-primes n) (let* ((ps (list->vector (primes (quotient n 2)))) (len (vector-length ps))) (define (p n) (vector-ref ps n)) (let loop ((lo 0) (hi (- len 1)) (max-lo 0) (max-hi (- len 1)) (max-prod 0)) (cond ((< hi lo) (list (p max-lo) (p max-hi) max-prod)) ((< n (* (p lo) (p hi))) (loop lo (- hi 1) max-lo max-hi max-prod)) ((< max-prod (* (p lo) (p hi))) (loop (+ lo 1) hi lo hi (* (p lo) (p hi)))) (else (loop (+ lo 1) hi max-lo max-hi max-prod))))))

The first clause returns a result, the second clause reduces the right pointer when the product exceeds *n*, the third clause saves a new maximum, and the fourth clause increases the left pointer when the product is less than the current maximum. The algorithm has time complexity O(*n* log log *n*) to compute the primes plus O(pi *n*) = O(*n* / log *n*) to find the maximum; you could improve the run time by caching primes. Here are our two examples:

> (max-prod-primes 27) (2 13 26) > (max-prod-primes 50) (7 7 49)

You can run the program at http://ideone.com/vhnVK4, where you will also see a simple prime sieve.

Scala:

In Python. Loop over the primes using a whel and is_prime, calculate the largest factor possible and get the largest second prime. Do this until the second prim is smaller than the first.

Another solution in Python. This runs a lot faster.

A quick solution in perl….

F# solution :

In Python.

@Paul: what is this rho_factors(i) function? Or is it from some library?

@Rutger. You can find it in the essay of @ProgrammingPraxis on primes. It is an implementation of Pollard’s rho.

Similar to Paul’s second solution. I treated the factor 2 separately, so that only odd numbers need to be considered in the loop.

An alternate version that sieves all the primes < n/2.

from sympy import sieve

def max_two_prime_product(n=100):

primes = list(sieve.primerange(0, n//2+1))

i,j = 0,len(primes) – 1

maxprod = (-1, 0, 0)

while i <= j:

prod = primes[i] * primes[j]

if prod < n:

maxprod = max(maxprod, (prod, primes[i], primes[j]))

i += 1

else:

j -= 1

return maxprod

With formatting:

Python solution. Uses a test to find the highest number below n that has two factors, and returns the factors of the detected number:

[…] Maximum product less than n of two primes […]

Two solutions, one fast but wrong and the other slow but right, both written in Racket Scheme.

#include

#include

int main()

{

int num,i,j,arr[25],l=0,max=0,f1=0,f2=0;

printf(“Enter the number\n”);

scanf(“%d”,&num);

for(i=2;i<num;i++)

{

for(j=2;j<i;j++)

if(i%j==0)

break;

if(i==j)

arr[l++] = i;

}

for(i=0;i<l;i++)

printf("%d\n",arr[i]);

for(i=0;i<l;i++)

for(j=0;jmax && arr[i]*arr[j] Max = %d\n”,f1,f2,max);

}