# The prime factors of 13195 are 5, 7, 13 and 29. # What is the largest prime factor of the number 600851475143 ? # source for formula: https://primes.utm.edu/prove/merged.html # the Sieve of Eratosthenes (ca 240 BC): from math import sqrt myNumber = int(raw_input("Enter a number to find its largest prime factor: ")) print "%s" %myNumber #make a list of all the integers less than or equal to myNumber myIntegers = [] i = 2 while i <= myNumber: myIntegers.append(i) i += 1 #find square root of myNumber myNumberSquared = sqrt(myNumber) #strike out multiples of all prime numbers less than or equal to the square root of myNumber count = 0 prime = myIntegers[0] while len(myIntegers) > 1 and myIntegers[0] <= myNumberSquared: for index, item in enumerate(myIntegers): if myIntegers[index] % prime == 0: del myIntegers[index] count += 1 prime = myIntegers[0] # print count #get the largest prime number largest_prime_factor = myIntegers[-1] print "The largest prime factor of ", myNumber, " is ", largest_prime_factor
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question