5
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Davislor
    Oct 29, 2023 at 0:50

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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. \$\endgroup\$
    – Timtech
    Oct 23, 2014 at 18:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – Martin R
    Oct 23, 2014 at 18:27
  • \$\begingroup\$ Oh, that's right. I was just thinking in terms of looping up till I. Thanks! \$\endgroup\$
    – Timtech
    Oct 23, 2014 at 18:47
  • \$\begingroup\$ Wait, no! I is updated every time; of course you need to re-calculate it. \$\endgroup\$
    – Timtech
    Oct 23, 2014 at 19:02
  • \$\begingroup\$ @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. \$\endgroup\$
    – Martin R
    Oct 23, 2014 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.