Euler Project #3 Largest prime factor timeout 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 &gt; 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 &gt; 1 and b &lt; (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.
It seems to me your second code example is wrong. You divide out only one prime factor and moving on testing for divisibility. If you enter, say: 8, it finds 2, divides it out, which gives 4, and will find 4 as largest prime that divides 8.

You have a lot of redundant tests, stepping b by one. 

Consider this:
Write any positive number n as n = m + 6*q (q may be 0). Except for the prime numbers 2 and 3: If m is divisible by 2, then so is n (because 6 is divisible by 2). If m is divisible by 3, then so is n (again, because 6 is divisible by 3). The only chances for n to be prime is, if m is 1 or 5. Not all of those numbers are prime, but if it is prime, it will be 1 or 5 modulo 6.

That will add a few lines of code, to explicitly test for primes 2 and 3. But after that, it should speed up your algorithm. Just remember to divide out all powers of a prime before moving on. A single test could look like this:

n = int(input())
num = n
max = 1

if n % 2 == 0:
    max = 2
    while n % 2 == 0:
        n //= 2

if n % 3 == 0:
    max = 3
    while n % 3 == 0: 
        n //= 3

b = 5
inc = 2

while n != 1:
    if n % b==0:
        max = b
        while n % b == 0: 
            n //= b

    b += inc
    if inc == 2:
        inc = 4
    else:
        inc = 2