# Project Euler problem 7

Back
10 May, 2016 @ 19:04

### The problem

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

In this example I started playing around with assembly functions and using the C standard call stack. Good simple exercise and motivation to keep finding things to do in the language. Since it seems, it would be almost impractical to write anything useful in x86 assembly!

# https://projecteuler.net/problem=7
#
# By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
# What is the 10 001st prime number?
#
# Solution by Joseph Mullins
# Answer: 104743
#
# compile with gcc euler_7.s
.global main
.text
main:
movq $1, %rcx
movq $0, %rdx
prime_counter:
add $2, %rcx
pushq %rdx
pushq %rcx
call check_power
popq %rcx
popq %rdx
cmp $0, %rax
je prime_counter
incq %rdx
cmp $10000, %rdx
je print
jmp prime_counter
# PURPOSE: Checks prime
# 0 is not a prime, anything else is
.type check_power, @function
check_power:
pushq %rbp
movq %rsp, %rbp
movq 16(%rbp), %rcx # get argument
movq $2, %rbx # Find half of the factor
movq $0, %rdx
movq %rcx, %rax
idivq %rbx
cmpq $0, %rdx # Though if divisible by 2, not a prime
je not_prime
cmpq $2, %rax
jle end_func
decq %rax
movq %rax, %r9
movq $2, %rbx
loop:
movq %rcx, %rax
movq $0, %rdx
idivq %rbx
cmpq $0, %rdx
je not_prime
cmpq %r9, %rbx # if we have got to half of it, then we know it must be prime
je end_func
incq %rbx
jmp loop
not_prime:
movq $0, %rax
end_func: # end of a function, %rax must hold return value before here
movq %rbp, %rsp
popq %rbp
ret
print:
movq $format, %rdi # set first paramter of printf, formatting
movq %rcx, %rsi # set 2nd paramter (the total value)
xorq %rax, %rax # printf is varags
call printf
ret
format:
.asciz "%200d\n"

### Answer

104743

Please sign in to post comments…