0
\$\begingroup\$

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.

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

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

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.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.