## Maximum Product Of Two Primes Less Than N

### August 28, 2015

Today we have a fun little exercise based on prime numbers.

Given an integer n > 4, find the maximum product of two prime numbers such that the product is less than n. For instance, when n = 27, the maximum is 2 * 13 = 26, and when n = 50, the maximum is 7 * 7 = 49.

Your task is to write a program to find the maximum product of two primes less than n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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