I have been recently trying my hands on Euler's Project through HackerRank and got stuck with project #3 where you have to find the Largest Prime Factor.
Question: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of a given number N?
I have written two different codes which both work for the first four problems in HackerRank but timeout on the last two. Please let me know how I can optimize my code further so that the timeout doesn't occur.
Code #1
for a in range(int(input())):
n = int(input())
b = n//2
i=1
if b%2==1:
i+=1
max=1
while b > 2:
if n%b==0:
isprime = True
for c in range(2,int(b**0.5)+1):
if b%c==0:
isprime = False
break;
if isprime:
max = b
break;
b-=i
if max==1:
max=n
print(max)
This one tries to find the first largest numbers which can divide a particular number and then tries to find whether it is a prime.
Code #2
for a in range(int(input())):
n = int(input())
num = n
b = 2
max=1
while n > 1 and b < (num//2)+1:
if n%b==0:
n//=b
max=b
b+=1
if max==1:
max=n
print(max)
This basically tries to find the last largest factor by multiple division.
a
andb
and why haven't you used more sensible names instead? Can you tell us more about your approach? \$\endgroup\$