3rd problem from project Euler

[Richard_SS]

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?
-
I have written a programm for solving this problem, it easily displays prime factors of 13195, but once I insert a bigger number (like 600851475143), a programm goes into an infinite loop, it returns neither error, nor answer. Please help, where is the problem in code?

My code:

import math
a = []
b = range(1,600851475143)

def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    sqr = int(math.sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

b = (filter(is_prime,b))

for i in b:
    if 600851475143 % i == 0:
        a.append(i)
    else:
        pass
print (a)
print("The largest prime factory is",a[-1::])

[DeaD_EyE]

You can improve the algorithm, if you define some primes.
Here an example:

def is_prime(n):
    primes = [
        2, 3, 5, 7, 11,
        13, 17, 19, 23,
        29, 31, 37, 41, 
        43, 47
    ]
    
    if n == 2:
        return True
    elif n % 2 == 0 or n <= 1:
        return False
    
    # speed up with known primes
    if n > 50 and any(n % p == 0 for p in primes):
        return False
 
    sqr = int(math.sqrt(n)) + 1
       
    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True

[Richard_SS]

You can improve the algorithm, if you define some primes. Here an example:

 def is_prime(n): primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 ] if n == 2: return True elif n % 2 == 0 or n <= 1: return False # speed up with known primes if n > 50 and any(n % p == 0 for p in primes): return False sqr = int(math.sqrt(n)) + 1 for divisor in range(3, sqr, 2): if n % divisor == 0: return False return True 

I got the point, but, don't you think it is too slow way to solve the problem? My programm is too slow for that big integer, and I guess I should think up about completely different algorithm to solve it, should i? Or i can somehow improve this one?

[perfringo]

If I casually observe it then it seems too brute-force approach.

As far as I understand one don't need to know all primes in range. One need to go up on only int(600851475142 / 2). Over that there can't be suitable factors. It seems to me, that it's not effective to calculate all primes in range and then try to find which are dividers. There is no point finding and checking primes which are large than half of range.

[Richard_SS]

If I casually observe it then it seems too brute-force approach. As far as I understand one don't need to know all primes in range. One need to go up on only int(600851475142 / 2). Over that there can't be suitable factors. It seems to me, that it's not effective to calculate all primes in range and then try to find which are dividers. There is no point finding and checking primes which are large than half of range.

You're right, i decided to take sqrt(x) of initial number, and i reduced execution time down to O(logn):D

[heiner55]

See similar thread:
https://python-forum.io/Thread-Juicy-hig...torization

[DeaD_EyE]

I think you forget, that for each call, the iterations are summed up.
This is interesting for big numbers.

If you check for example the number 179424673, the sum of total iterations is in the range of:

sum(int(math.sqrt(i)) + 1 for i in range(3, 179424673))
# one minute later....

Output:
1602346003985

Of course you won't hit the maximum possible iterations, because some values are sorted out
by dividing with already known primes.
Calling the same function very often, causes the problem.