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

• 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. – 200_success Jan 12 at 6:27
• Who are a and b and why haven't you used more sensible names instead? Can you tell us more about your approach? – Mast Jan 13 at 11:38

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

• 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. – Zeta Jan 12 at 8:46
• @Zeta Understood. Thanks for the heads up! – jgb Jan 12 at 10:05

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.