Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
This solution was a little tricky. The best case scenario is if our number—let’s call it $ n$—is a perfect square. In this case, the only admissible prime is the root square of $ n$ repeated twice.
Playing with square numbers
Using this idea, the algorithm goes as follow.
- First, make a list with all the odd numbers until the integer part of the square root of $ n$.
- Then, add the number 2 to this list because it is a prime number.
- Next, compute the modulo of $ n$ with each element of the list, call it $ p$.
- Divide $n$ by each $p$. If the quotient is an integer, then change $n$ by this quotient.
- Finally, iterate until $n$ is equal to $1$.
My implementation just works, but of course there is room for improvements. If you have any suggestion please let me know them in the comments.
import math # One large number number = 600851475143 # The list of prime factors prime_factors =  # A control variable to # know when we finish we_are_done = False while not we_are_done: # The best case scenario is if # number = some_prime^2 sqrt_root_number = int(math.sqrt(number)) # Create a list of posible primes # 2, 3, 5, 7, ... seq_divisors = range(3, sqrt_root_number, 2) seq_divisors.insert(0,2) for factor in seq_divisors: # Checking if divisible if number % factor == 0: # If factor is divisible then change # the number by the quotient number = number / factor # add the prime to the list prime_factors.append(factor) # We're not finished yet! we_are_done = False break else: # There is not more factors we_are_done = True # Just to not include 1 in the list if number != 1: prime_factors.append(number) print prime_factors print max(prime_factors)