Calculate highest prime factor very slow Sometimes when I write a Python 3.x script with too many nested loops and some big values it just takes too long to give the answer. How can I optimize my code so that it runs faster, or where should I optimize?

def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n &lt; 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n &amp; 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True



ans=0
for i in range(600851475143,0,-1):
if 600851475143%i==0:
    if isprime(i)==True:
        ans=i
        break;
    else:
        continue;
print(ans)


This program should calculate the highest prime factor of the number 600851475143, but it didn't give any answer for half an hour.
You want to compute the largest prime factor of a given number, but it is actually more efficient to look for the smallest prime factors first (and I am just repeating my arguments from my answer). If you test the possible factors in increasing order and divide the given number by a found factor as much as possible, then each found factor is necessarily a prime number. This means that no primality test is needed at all.

This leads to the following function (which is just a translation of the referenced
answer to Python):

def max_prime_factor(n):
    '''find the largest prime factor of integer n'''

    largest_factor = 1
    i = 2

    # i is a possible *smallest* factor of the (remaining) number n.
    # If i * i &gt; n then n is either 1 or a prime number.
    while i * i &lt;= n:
        if n % i == 0:
            largest_factor = i
            # Divide by the highest possible power of the found factor:
            while n % i == 0:
                n //= i
        i = 3 if i == 2 else i + 2

    if n &gt; 1:
        # n is a prime number and therefore the largest prime factor of the 
        # original number.
        largest_factor = n

    return largest_factor


Timing for the largest prime factor of 600851475143 (on a 3,5 GHz Intel Core i5 iMac):


Your method: 43 seconds
Sieve method from @wei2912: 0.2 seconds
Above method: 0.016 seconds