-2

I was trying Project Euler Problem 3: What is the largest prime factor of the number 600851475143 ? My code is working for random 4 digit numbers. However my code is just not compiling. It has been 15 minutes now.

I think this has something to do with "efficiency of algorithms". I am about to join college for Computer Science and Engineering course so I thought it would be a great idea if I practiced coding in Python. Is my code not efficient? Should I study CLRS now before going any further? I have already completed the basics of Python (from Udacity).

#What is the largest prime factor of the number 600851475143 ?
factorlist=[]
def prime(num):                                             #primetesterfunction
    primecount=0
    for factors in range(2,num):
        if num%factors==0:
            return False
        else:
            primecount+=1
    if primecount==num-2:
        return True

num=int(input("Enter Number: "))
for x in range(2,num+1):
    if num%x==0 and prime(x)==True:
        factorlist.append(x)
    else:
        continue
print("The largest prime factor of {} is {}".format(num,factorlist[-1]))

It's been 18 minutes now and still no result...

Shiladitya Mukherjee
  • 19
  • 4
  • There's no such thing as *compilation* in Python. You probably mean *execution*. – goodvibration Jun 29 '19 at 09:11
  • It shouldn't be a surprise that a nested loop with that many iterations takes a long time – Sayse Jun 29 '19 at 09:19
  • [Cross site duplicate](https://codereview.stackexchange.com/q/104997) – Sayse Jun 29 '19 at 09:21
  • 1
    No one said your question was wrong, if you'd clicked on either of the links I posted instead of being rude you'd have seen they're the *exact same question* – Sayse Jun 29 '19 at 10:16

1 Answers1

0

There is no such thing as compilation in Python; you probably mean execution.

It takes less than a second to get the answer:

n = 600851475143

p = 2

while n > 1:
    if n % p == 0:
        while n % p == 0:
            n /= p
        largest = p
    p += 1

print(largest) # 6857

So your code is either extremely inefficient, or it is plain wrong.

Sayse
  • 42,633
  • 14
  • 77
  • 146
goodvibration
  • 5,980
  • 4
  • 28
  • 61
  • Pyc files? I've edited out all of the unneeded commentary – Sayse Jun 29 '19 at 09:30
  • Yeah look I don't know the first thing about "compilation" or "execution" technically. I thought that they all mean execution loosely. And my code is not wrong. I have tested it for many 4 digit numbers. And I don't understand why you got your answer in 2 seconds. That is why I asked whether I should read theoretical aspects of efficiency. – Shiladitya Mukherjee Jun 29 '19 at 09:31
  • I do understand your code though. Its neat. – Shiladitya Mukherjee Jun 29 '19 at 09:33