25 Mar, 2016 @ 15:42

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 ?

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!

# 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"

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.

# 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"

Answer: 6857

Please sign in to post comments…