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.
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.
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.