## 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.

Pages: 1 2

### 13 Responses to “Maximum Product Of Two Primes Less Than N”

1. FA said

Scala:

```package programmingpraxis

//https://programmingpraxis.com/2015/08/28/maximum-product-of-two-primes-less-than-n/
object PrimesProduct {
def sieve(numbers: Stream[Int]): Stream[Int] = {
if (numbers.isEmpty) Stream()
else numbers.head #:: sieve(numbers.tail filter { _ % numbers.head != 0 })
} //> sieve: (numbers: Stream[Int])Stream[Int]

def primes(n: Int): Seq[Int] = sieve(2 to n toStream) toList

def primesProduct(n: Int): Tuple3[Int, Int, Int] = {
(for (p1 <- primes(n / 2); p2 <- primes(n / 2) if p1 * p2 < n) yield (p1 * p2, p1, p2)).max
} //> primesProduct: (n: Int)(Int, Int, Int)

primesProduct(27) //> res1: (Int, Int, Int) = (26,13,2)
primesProduct(50) //> res2: (Int, Int, Int) = (49,7,7)
}
```
2. Paul said

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.

```def max_prime(n):
if n <= 6:
return 4
maxprod = 0
for p1 in accumulate(chain((2,1,2,2), cycle((4,2,4,2,4,6,2,6)))):
if not is_prime(p1): continue
if p1 ** 2 >= n: break
f = (n - 1) // p1
if f % 2 == 0: f -= 1  # make f odd
while not is_prime(f): f -= 2 # find largest prime <= f
maxprod = max(maxprod, p1 * f)
if maxprod == n - 1: break
return maxprod
```
3. Paul said

Another solution in Python. This runs a lot faster.

```def max_prime(n):
for i in range(n - 1, 0, -1):
f = rho_factors(i)
if len(f) == 2:
return i
```
4. A quick solution in perl….

```my \$x = shift @ARGV;
while(--\$x>4) {
die "\$x\n" if nf(\$x);
}

sub nf {
my \$x=shift;
my \$n = 0;
for( \$y=2; \$y<=\$x; \$y++) {
next if \$x%\$y;
\$n++;
return 0 if \$n>2;
\$x/=\$y;
redo
}
return 1 if \$n == 2;
return 0;
}
```
5. klettier said

F# solution :

```let isPrime i =
let mid = i / 2
let rec loop n div =
match n, div with
| a, _ when a <= 1 -> false
| _, 1 -> true
| a, b when a % b = 0 -> false
| a, b -> loop a (b-1)
loop i mid

let primes n =
seq {
for i in 1..n do
if isPrime i  then yield i
}

let ``Maximum Product Of Two Primes Less Than N`` n =
let mutable res = 0
let mid = n / 2
let arr = primes mid
let mutable j,k,rj,rk = 0,0,0,0
for a in arr do
for b in arr do
let t = a*b
if (t > res) && (t < n) then
res <- t
rj <- a ; rk <- b
rj,rk,res

``Maximum Product Of Two Primes Less Than N`` 27;; // (2, 13, 26)
``Maximum Product Of Two Primes Less Than N`` 50;; // (7, 7, 49)
``Maximum Product Of Two Primes Less Than N`` 100;; // (5, 19, 95)
```
6. Rutger said

In Python.

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

```# old implementation I once made, returns a list of all prime factors of number
def factorize(number):
factors = []
while not (number % 2):
number = number / 2
factors.append(2)
i = 3
while i <= number**0.5 and number-1:
if not (number % i):
factors.append(i)
number = number / i
else:
i += 2
if number != 1 and i >= number**0.5:
factors.append(number)
return factors

def max_prod_primes_less_than_n(n):
for i in range(n-1, 1, -1):
f = factorize(i)
if len(f) == 2:
return f
return None

for n in range(100):
print n, max_prod_primes_less_than_n(n)

# output:
# 0 None
# 1 None
# 2 None
# 3 None
# 4 None
# 5 [2, 2]
# 6 [2, 2]
# 7 [2, 3]
# 8 [2, 3]
# 9 [2, 3]
# 10 [3, 3]
# 11 [2, 5]
# 12 [2, 5]
# 13 [2, 5]
# 14 [2, 5]
# 15 [2, 7]
# 16 [3, 5]
# 17 [3, 5]
# 18 [3, 5]
# 19 [3, 5]
# 20 [3, 5]
# 21 [3, 5]
# 22 [3, 7]
# 23 [2, 11]
# 24 [2, 11]
# 25 [2, 11]
# 26 [5, 5]
# 27 [2, 13]
# 28 [2, 13]
# 29 [2, 13]
# 30 [2, 13]
# 31 [2, 13]
# 32 [2, 13]
# 33 [2, 13]
# 34 [3, 11]
# 35 [2, 17]
# 36 [5, 7]
# 37 [5, 7]
# 38 [5, 7]
# 39 [2, 19]
# 40 [3, 13]
# 41 [3, 13]
# 42 [3, 13]
# 43 [3, 13]
# 44 [3, 13]
# 45 [3, 13]
# 46 [3, 13]
# 47 [2, 23]
# 48 [2, 23]
# 49 [2, 23]
# 50 [7, 7]
# 51 [7, 7]
# 52 [3, 17]
# 53 [3, 17]
# 54 [3, 17]
# 55 [3, 17]
# 56 [5, 11]
# 57 [5, 11]
# 58 [3, 19]
# 59 [2, 29]
# 60 [2, 29]
# 61 [2, 29]
# 62 [2, 29]
# 63 [2, 31]
# 64 [2, 31]
# 65 [2, 31]
# 66 [5, 13]
# 67 [5, 13]
# 68 [5, 13]
# 69 [5, 13]
# 70 [3, 23]
# 71 [3, 23]
# 72 [3, 23]
# 73 [3, 23]
# 74 [3, 23]
# 75 [2, 37]
# 76 [2, 37]
# 77 [2, 37]
# 78 [7, 11]
# 79 [7, 11]
# 80 [7, 11]
# 81 [7, 11]
# 82 [7, 11]
# 83 [2, 41]
# 84 [2, 41]
# 85 [2, 41]
# 86 [5, 17]
# 87 [2, 43]
# 88 [3, 29]
# 89 [3, 29]
# 90 [3, 29]
# 91 [3, 29]
# 92 [7, 13]
# 93 [7, 13]
# 94 [3, 31]
# 95 [2, 47]
# 96 [5, 19]
# 97 [5, 19]
# 98 [5, 19]
# 99 [5, 19]
100 [5, 19]
```
7. Paul said

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

8. Mike said

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

```from sympy import prevprime, factoring

def max_two_prime_product(n=100):
p = 2 * prevprime(n//2 + 1)
for i in range(n-2 if n&1 else n-1, p, -2):
fs = factorint(i)
if len(fs) == 2 == sum(fs.values()):
return i, sorted(fs.keys())
return p, [2, p//2]

```

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

9. Mike said

With formatting:

```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
```
10. Brett Warren said

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

```__author__ = 'Brett Warren'

from MoreMath import isprime

def lowest_prime_factor(number):
for candidate in range(2, number):
if not number % candidate:
return candidate

def lowest_duo_prime_product(number):
for product_total in reversed(range(1, number)):
prime1 = lowest_prime_factor(product_total)
other_product = int(product_total/prime1)
if isprime(other_product):
return [prime1, other_product]

if __name__ == "__main__":
print(lowest_duo_prime_product(73259856))
```
11. […] Maximum product less than n of two primes […]

12. r. clayton said

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

13. Mayur Lokare said

#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);
}