Posts Tagged ‘computr’

Python: Largest Prime Factor

Python: Largest Prime Factor
Problem No.3 on ProjectEuler

Quite easy one to solve, in this task we need to get all the factors of a given number, then to print out the largest prime one.

To solve this with a Large Number I search the net and i fond an article explain it. So here i am putting it in points.

Factors of Large Numbers:
1. First ask if the number N is (Even or Odd)?
2. If the number N is Even, then factors=(2) then, the new N = N Divide by 2.
3. If the number N is Ood, then start form 3 and get/find smallest prime factors (SPF) of it.
4. Add the smallest prime factors to factors list.
5. Then, the new N = N Divide by smallest prime factors (SPF).
6. If the new N is Even goto line 2, If the new N is Odd goto line 3.

The Code:

# Largest prime factor
# Problem No.3
# Solved

def factors_of_n(num):


while a <= num:

if num%a==0:

return int(a)


a = a + 1

# This is the number from ProjectEuler
num = 600851475143
temp_num = num
facto_back =0
p_factors =[]

while temp_num > 1 :

if temp_num%2==0 :


temp_num = temp_num / 2


facto_back =factors_of_n(temp_num)


temp_num = temp_num / facto_back

print(‘\n Largest Prime Factor of {} is {}’.format(num,max(p_factors)))