; Written by bitRAKE
; The GetNearestPrime function retrieves a prime which is the nearest nn.
; In: Unsigned Integer, less than 2^64
; Return value: RCX (prime)
GetNearestPrime proc nn:QWORD
;rcx = nn
cmp rcx, 3 ; Special cases are clamped to prime two.
jc @two
bt ecx, 0 ; Adjust for even numbers, and counteract
adc rcx, 1 ; below subtraction by two.
jc @over ; Two overflow case require special handling.
@next_candidate:
mov r9d, 1 ; N^2
mov r8d, 1 ; N, divisor
sub rcx, 2 ; prior odd canidate
@try:
lea rdx, [r8*4 + 4] ; next odd square, (N+2)^2 = N^2 +4N +4
sub r8, -2 ; next odd number, N+2
add r9, rdx
jc @prime
mov rax, rcx
xor edx, edx
cmp rcx, r9 ; If the square of the divisor exceeds
jc @prime ; the number it must be prime.
div r8
test rdx, rdx
jnz @try
cmp rcx, 4
jnc @next_candidate
mov ecx,3
@prime:
ret
@two:
mov ecx,2
ret
@over:
mov rcx,(1 shl 64) - 59 ;the largest prime < 2^64
ret
;RCX is always prime, CF=1
GetNearestPrime endp
