Home > Problem, Projects/Experiments, Python > Python: Largest Prime Factor

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
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s