Project Euler 3 on Python

Question

I'm thinking about the 3rd problem on Project Euler. I already have the solution, but it's too long.

Here is my code:

def check_prime_number(prime_number):

    for i in range(2, int(prime_number / 2)):
        
        if prime_number % i == 0:
            return False
            
    return True

def find_divisors(number):

    for divisor in range(int(number / 2), 2, -1):

        if check_prime_number(divisor) and number % divisor == 0:
            number /= divisor
            
            print(divisor)
            break

find_divisors(600851475143)

How to work with long numbers like 600581475143 in Python?

Python has infinite precision integers. What is the exact problem? — Mad Physicist, Jul 09 '20 at 17:09

Balaji Ambresh · Answer 1 · 2020-07-09T17:43:06.120

0

Here you go:

def max_prime_divisor(limit):
    primes = [2]
    answer = None
    if limit % 2 == 0:
        answer = 2
    for i in range(3, int(limit ** .5) + 1, 2):
        inner_limit = int(i ** .5)
        is_prime = True
        for prime in primes:
            if prime > inner_limit:
                break
            if i % prime == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
            if limit % i == 0:
                answer = i
    return answer


print(max_prime_divisor(600851475143))

Output:

`

edited Jul 09 '20 at 17:43

answered Jul 09 '20 at 17:10

Balaji Ambresh

4,977
2
5
17

`def check_prime_number(prime_number): for i in range(2, int(prime_number / 2)): if prime_number % i == 0: return False return True def find_divisors(number): for divisor in range(2, int(number / 2)): if check_prime_number(divisor) and number % divisor == 0: number /= divisor print(divisor) find_divisors(600851475143)` – Jul 09 '20 at 17:27
Output: `71, 839, 1471, 6857`. – Jul 09 '20 at 17:27
1

@MarK The code you pasted corresponds to the one in the post. Our approaches are different. You're checking for half the values. I'm checking for `sqare root` of the values. Also, the division check involves checking only across the prime numbers. – Balaji Ambresh Jul 09 '20 at 17:29
@MarK even numbers can't be prime divisors. So, look at the indices of the loop. – Balaji Ambresh Jul 09 '20 at 17:33
But does it count the `71, 839, 1471 6857` output as a solution?( ﾟヮﾟ) – Jul 09 '20 at 17:38
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/217554/discussion-between-mark-and-balaji-ambresh). – Jul 09 '20 at 17:44

Project Euler 3 on Python

1 Answers1