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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: