## 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 thann. For instance, whenn= 27, the maximum is 2 * 13 = 26, and whenn= 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.

Advertisements

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

}