I wanted to create an algorithm that could be used to test whether a number is prime or not. I have previously written a program that finds the prime factors of a number and this can be used to determine whether a number is prime or not but it isn't very quick for this purpose. I wanted a faster algorithm that could give a yes/no answer for all positive integers up to about 1000 and could be extended to larger numbers if required.
One issue with the fx-50F calculator is that there is no quotient/remainder function. So if we divide 101 by 7 then we know that the quotient is 14 and the remainder is 3 (i.e 101=14x7+3). If the remainder was 0 then we would have known that 101 was divisible by 7.
One way round this is to use the sine function. We have that sin(πx)=0 if x is an integer and not otherwise (you need to use the fx-50F in radians mode - [SHIFT] [SETUP] [2]). Thus if we let x=101/7=14.428..., then sin(πx)=0.974...whereas if we let x=99/3=33, then sin(πx)=0. So we have a way of determining whether one positive integer is divisible by another.
This forms the basis of the processing. For a given number N we can trial divide N by each of the prime numbers P which are less than some prime M, say. If N is divisible by P then we can set a flag to indicate that N is not prime. Clearly, if N is one of the prime numbers P, then we need to check this and flag it accordingly. This method will be accurate as long as N is is less than M2.
