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

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: