Joseph Mullins

Programmer | Security | Automation

joseph@ropeney.com

# Project Euler 3

While still trying to keep using the standard 4 registers, rax, rbx, rcx, rdx this problem was fairly fun on the brute-force approach. Reducing the number to 29 made for easy debugging. Doing some research into finding prime numbers and seeing solutions people have done for this problem, I reverse engineered there solution and made it into Assembly.

The problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

### Brute-force Approach

This approach is the first solution people do to most problems, work out how to get there with a smaller number, then repeat until you are there. Optimising first is the root of all evil, so we implement this solution then let the numbers get big and see if its still quick enough. This seems a bit counter productive in Assembly, as why would we write assembly if we weren't aiming for speed! (Yes I know specific control might be a thing too). Well, I didn't envision such a large number taking so long, 29 was almost instant!

### The Code

```# https://projecteuler.net/problem=3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
#
# Solution by Joseph Mullins
#
# Compile with gcc euler_3.s

.global main

.text

main:
mov \$600851475143, %rcx         # The number
mov \$0, %rdx
mov %rcx, %rax
mov \$2, %rbx
div %rbx                        # Half is the max the prime factor can be
cmp \$0, %rdx                    # If it was divisible by 2 then we need to subtract 1
jne setup
dec %rax

setup:
mov %rax, %rbx                  # rbx will hold our current count
push %rcx

loop:
pop %rcx
sub \$2, %rbx                       # Start the countdown to find highest factor
mov %rcx, %rax                  # set up to see if starting number is divisible by rdx
mov \$0, %rdx
div %rbx
cmp \$0, %rdx                    # Check if remainder is 0, if so then check if its a prime
je check_if_prime
push %rcx
jmp loop

check_if_prime:
push %rcx                       # Save our prime master number
mov \$2, %rcx                    # Start our checking if prime number at 2

prime_loop:
cmp %rcx, %rbx                  # if rcx got high enough to only be divisible by itself, its prime
je print
mov %rbx, %rax                  # divide the current number, by 2..n
mov \$0, %rdx
div %rcx
cmp \$0, %rdx                    # if remainder is 0, it was divisible by something other then itself
je loop
inc %rcx                        # increment and keep going
jmp prime_loop

print:
pop %rdx                        # So everythings off the stack
mov \$format, %rdi
mov %rbx, %rsi
xor %rax, %rax

call printf
ret

format:
.asciz "%200d\n"
```

### A Better Algorithm

Well trying to find the largest prime factor with this approach for 29 was quick! But finding it for 600851475143 was no small task. ./a.out 1086.47s user 0.03s system 99% cpu 18:06.58 (18 minutes) on my computer. So researching a better method was required. I looked at how other people were solving this problem in other languages and came across Jason B. Hill, in his solution at http://code.jasonbhill.com/c/project-euler-problem-3/, he implemented a smarter algorithm. A simple overview of the algorithm, is it works by dividing itself by a counter starting at 1. Once it finds a counter that is a prime, it divides itself by that prime. The result is then stored in a variable and the counter increases. The result is then divided by the next prime, repeating until the result / counter = 1. We then have our prime number.

### The Better Algorithm

```# https://projecteuler.net/problem=3
# The prime factors of 13195 are 5, 7, 13 and 29.
# What is the largest prime factor of the number 600851475143 ?
#
# Using algorithm taken from:
# http://code.jasonbhill.com/c/project-euler-problem-3/
# Works by dividing itself by a counter, untill it / counter can't be divided by anything
# other then 1 and itself
#
# Solution by Joseph Mullins
#
# Compile with gcc euler_3.s

.global main

.text

main:
mov \$600851475143, %rcx     # The number
mov \$1, %rbx                # rbx will hold our current count

loop:
add \$2, %rbx                # count in 2's as even numbers can't be a prime factorial
mov %rcx, %rax              # setup for divison
mov \$0, %rdx
div %rbx
cmp \$0, %rdx                # Check if remainder is 0, if so then set into rdx
je  set_rcx
cmp \$1, %rax                # if the division was equal to one, we have our largest prime
je print                    # so print it if that was the case
jmp loop                    # repeat if it wasnt

set_rcx:
mov %rax, %rcx              # store the result of the divison into rcx
jmp loop

print:
mov \$format, %rdi
mov %rcx, %rsi
xor %rax, %rax

call printf
ret

format:
.asciz "%200d\n"
```