Thursday, August 16, 2012

Python program to find the largest prime factor of the number

Recently I started learning Python. Having programmed in C, C++ and Java up to now, I found it rather different, but easy :). Here is my small and first ("Hello World" is too boring now!) program in Python-

#Computes the largest prime factor for the number
#Solution for Problem 3 on Project Euler.net

import math

x = int(raw_input('Enter Number : '))
max_factor = 2

i = (x+1)/2

while i > 1:
    if x % i == 0:
        j = 2
        while j <= int(math.sqrt(i)):
            if i % j == 0:
                break
            j = j + 1
        else:
            max_factor = i
            break
    i = i - 1

print max_factor


To find all the prime factors just use a list instead of max_factor, and keep appending "i" to it. Also remove the 'break' statement in 'else:'.

No comments:

Post a Comment