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.
Programming Praxis 
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) }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 maxprodAnother 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 iA quick solution in perl….
my $x = shift @ARGV; while(--$x>4) { die "$x\n" if nf($x); } die "No answer\n"; 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; }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)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]@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.
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
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 maxprodPython 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))[…] 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);
}