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.

• 200_success: Please fix your indentation. The easiest way to post code is to paste it into the question editor, highlight it, and press Ctrl-K to mark it as a code block.
• Mast: Who are a and b and why haven't you used more sensible names instead? Can you tell us more about your approach?

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

• Zeta: Welcome to Code Review. Please don't answer off-topic questions. As long as the indentation in the original question is off (and thus the code broken), the question is considered off-topic.

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.