"Is a number prime?"

Question

I've come up with a very efficient way of finding if a number is prime, using TI-BASIC for use with TI-83/84/+/SE calculators. I am trying to optimize it however possible.

:Input "NUMBER: ",A
:If A<2 or fPart(A
:Then
:Disp "INVALID INPUT"
:Stop
:End
:0→B
:2→I
:While I<A and not(B
:If 0=fPart(A/I
:1→B
:I+2→I
:If I=4
:3→I
:End
:If B
:Disp "NOT"
:Disp "PRIME"

A few notes:

• Lines 2-6 are for validating input, and don't affect the effectiveness of the program.
• The closing "s on line 4 and the last two lines are not necessary, but I added them so the syntax would highlight nicely here.
• Lines 12-14 are for speeding up the loop doubly; instead of incrementing by 1 each time, it is by 2, with the If to offset the 4 to 3 on the first run.
• The not(B was very efficient, to end the loop whenever a match to identify the number as a composite number is found.

• Davislor: In practice, if you have enough memory, the most optimal solution is to store a lookup table (of some kind) of prime numbers and look up the number being queried. This can be pre-calculated, or done by a sieve. A list of all primes up to 65,536 is enough to test all integers up to 4.3 billion by trial division.

Answer 1

I do not speak TI-BASIC, so I cannot review the style, coding conventions etc. But there are two possible optimizations:

• If a number A is composite then it must have a factor that is less than or equal to √(A). So you can replace

   :While I<A and not(B
  

with:

 :√(A)→S
 :While I≤S and not(B

This reduces the number of trial divisions substantially if the input is a prime number.

• Check the divisibility by 2 first, and then loop just over the odd numbers I = 3, 5, 7, .... This saves you from checking

   :If I=4
   :3→I
  

in each loop iteration.

• Timtech: I can't really change my code here now that it's posted, but I had :While I²<A and not(B but the square didn't copy over for some reason... and thanks for the second suggestion.
• Martin R: @Timtech: OK, but computing the square root once instead of I^2 in each iteration is usually faster. But I don't know if that applies to your calculator.
• Timtech: Oh, that's right. I was just thinking in terms of looping up till I. Thanks!
• Timtech: Wait, no! I is updated every time; of course you need to re-calculate it.
• Martin R: @Timtech: My suggestion was to calculate S = sqrt(A) once, so that you don't have to calculate I^2 in each iteration. While I^2 < A is replaced by While I <= S.