The Roberto Selbach Chronicles

About |  Blog |  Archive

Euler 3

Posted on by Roberto's Chronicles

So the other night I was a bit bored and decided to do something to pass the time. I first came across Project Euler a while ago, but had never gone further than problem #1. Boredom is a great motivator and I went through problems #2 thru #9 last night and I decided to post my solutions in search of better ones. Feel free to comment with your suggestions.

Project Euler’s Problem #3 statement is —

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

What is the largest prime factor of the number 600851475143 ?

My solution is really ugly and is basically dumb-, brute-force.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#!/usr/bin/python

import math

top_number = 600851475143

def is_divisor(divisor):
        return top_number % divisor == 0

def is_prime(divided):
        divisor = 3
        sqrt_divided = math.sqrt(divided)
        if divided == 1:
                return true
        while divisor <= sqrt_divided:
                if divided == divisor:
                        return True
                elif divided % divisor == 0:
                        return False
                else:
                        divisor += 2
        return True

def main():
        count = 3
        go_to = top_number

        first_list =[]
        while count <= go_to:
                if is_divisor(count):
                        first_list.append(count)
                        go_to = top_number / count
                        first_list.append(go_to)

                count += 2

        second_list = map(is_prime, first_list)
        print "%s" % max(zip(second_list, first_list))[-1]

if __name__ == "__main__":
        main()