Skip to content

Instantly share code, notes, and snippets.

@julius-datajunkie
Last active December 26, 2015 03:29
Show Gist options
  • Save julius-datajunkie/7086371 to your computer and use it in GitHub Desktop.
Save julius-datajunkie/7086371 to your computer and use it in GitHub Desktop.
This is very inefficient algorithm to solve the problem. It takes Python more than 5 minutes to solve the problem with the number given
import unittest
from math import sqrt
def isPrime(i):
if (i == 2 or i == 3):
return True
else:
for j in range(3, int(sqrt(i)+1)):
if ( i % j == 0):
return False
return True
def FindLargestPrimeFactor(number):
'''
Input: a number
Output: The largest prime factor of the number
Essentially checking for if all possible integers less then sqrt(number) are prime or not, then
return the largest one found.
'''
max = 0
for i in range(3,int(sqrt(number)+1)):
if isPrime(i):
if (number % i == 0):
max = i
return max
def FindLargestPrimeFactor_2(number):
'''
'''
class Test(unittest.TestCase):
def test_FindLargestPrimeFactor(self):
self.assertEqual(FindLargestPrimeFactor(13195),29)
if __name__ == '__main__':
unittest.main(exit=False)
print(FindLargestPrimeFactor(600851475143))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment