Archive
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)))
|
Taking pictures is not my main daily practices, but when i start playing with my camera, i really enjoy my self.
Thanks for visiting my Space..
Ali's Photography Space... 