Euler Project #3 Largest prime factor timeout

Question

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.

Answer 1

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

Answer 2

It may be more optimal to use the Sieve of Eratosthenes because it may reuse calculations better than the given approaches. This would be a bottom-up approach rather than a top-down approach but it is a very efficient bottom-up approach.

You just need to take the extra step where for each entry you find to be prime, you check if it is a factor of the given number. You also have a early stopping condition - the prime factor must be <=sqrt(N). So you need a sieve for 1 ... sqrt(N)

Note that there are ways to work with a segmented sieve, to minimise the amount of memory used at once.