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