Finding 6648031207514 ' s largest prime factor

Question

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

Answer 1

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