Archive

Archive for July 1, 2019

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):

a=3

while a <= num:

if num%a==0:

return int(a)

break

a = a + 1


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

while temp_num > 1 :

if temp_num%2==0 :

p_factors.append(2)

temp_num = temp_num / 2

else:

facto_back =factors_of_n(temp_num)

p_factors.append(facto_back)

temp_num = temp_num / facto_back

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




Advertisements