1

this is my first question here.

I have been solving eulerproject.net questions and after getting a correct answer for the given input I wanted to try different ones to check whether my code was working properly. Seems like it doesn't.

Largest prime factor should be 1137193159 but I get 79. Of course because of the upper limit I have put here. However, if I increase the upper limit even a little my code gets super slow.

This is the function I have used for finding the largest prime factor 

def largest_prime_factor(n) :

upper_limit = math.trunc((n**0.5))

while(1) : 

    for num in range(upper_limit, 2, -1) : 
        if n % num == 0 :
            if(isPrime(num)) : 
                return num 
        else : 
            pass

    if(isPrime(n)) : 
        return n

Here is the isprime method 

## taken from : https://stackoverflow.com/questions/15285534/isprime-function-for-python-language
def isPrime(n):
if n==2 or n==3: return True
if n%2==0 or n<2: return False
for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
    if n%i==0:
        return False    

return True

Thanks in advance

Kutay Eroglu
  • 73
  • 1
  • 5
  • 3
    You can change the `isPrime()` method, by using sieve of erastosthenes. Since you're only checking root(n) numbers, you'll have to create a sieve of size root(n). Then your time complexity will come down to O(root(n)) from O(n). – Mooncrater May 31 '20 at 09:53
  • @Mooncrater--[Complexity of Sieve of Erastosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity) is O(n log log n), which makes it good for finding all primes in a range. Considering this overhead how is the complexity reduced to O(sqrt(n)) for finding the largest prime factor for one number using the sieve? Meaning is_prime would become O(1) using a list of primes, but it first incurred the O(n*log log n) overhead to find all the primes. – DarrylG May 31 '20 at 11:14
  • Yeah man you get the point. – Mooncrater May 31 '20 at 12:29
  • I created a custom factorization module that use Sieve of Erastohenes and is non probabilistic. It can also reduce larger numbers that PARI/ECM can't factor via straight factorization, but is can be reduced using the pseudoprimes it creates on PARI/ECM so used in conjunction you can reduce the number 2*1200-1, which you can't quickly do straight up using PARI/ECM. If your interested in it you can find it here: https://github.com/oppressionslayer/primalitytest/ It also includes a super fast modulus reduction technique for powers of two – oppressionslayer May 31 '20 at 12:51

1 Answers1

2

Fixes to software

  • The Largest prime factor can be greater than sqrt(n). Software only returns up to sqrt(n)
  • incorrect range 'range(upper_limit, 2, -1) :' should be for num in range(upper_limit, 1, -1) : since stop point is exclusive
  • Should not have while loop around for loop
  • No need to check if the number is prime after for loop

Issue

Above Fixes Code, but Remaining Issue is algorithm complexity will be O(n) since

  1. O(sqrt(n)) size of for loop
  2. O(sqrt(n)) to run is_prime in each loop
  3. 1&2 makes complexity O(n)

Refactored Code

import math

def largest_prime_factor(n) :

  upper_limit = math.trunc((n**0.5))

  for num in range(upper_limit, 1, -1) : # use 1 for lower limit
      if n % num == 0 :
          if(isPrime(num)) : 
              return max(num, n // num)  # to include values above sqrt(n)

  #if(isPrime(n)) : 
  return n  # We know it's prime since no divisors in for loop

def isPrime(n):
  if n==2 or n==3: return True
  if n%2==0 or n<2: return False
  for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
      if n%i==0:
          return False    

  return True

Usage

print(largest_prime_factor(1137193159 )) # Output: 1137193159 
# Timing (using timeit):  0.01357 seconds per calculation

Better Algorithm (closer to O(sqrt(n)*log(n)) Time Complexity

Reference

Advantage

  • Sieve of Erastosenes is better for a batch of numbers --O(n log log n) to find primes in range, then log (n) per number. This wold be O(n*log(n)) for a single number.

  • Current algorithm is better for a single number--no setup, so O(sqrt(n)*log(n)) per number.

    A function to find largest prime factor

    def max_prime_factor(n): 

    # Initialize the maximum prime factor 
# variable with the lowest one 
maxPrime = -1

# Remove factors of two 
while n % 2 == 0: 
  max_prime = 2
  n //= 2

# Removed all factors of two so n is odd 
# For loop size sqrt(n) / 2 
for i in range(3, int(math.sqrt(n)) + 1, 2): 
  while n % i == 0: 
                  # O(log(n)) divisors
    max_prime = i # i must be prime since all 
                  # the lower prime divisors 
                  # of n have been factored out
    n //= i 

# Check if
# n is a prime number  
if n > 2: 
  max_prime = n 

return max_prime

Comparison

Timing for n = 1137193159

  • max_prime_factor: .0061 seconds
  • largest_prime_factor: 0.01357 seconds

Thus: ~2X improvement for this case over the original code

DarrylG
  • 16,732
  • 2
  • 17
  • 23